数据结构学习笔记Day2（连载中）

连续存储与离散存储

数据结构【把所有的结点用一根直线穿起来】

（1）连续存储（数组）

1.什么叫做数组

    元素类型相同，大小相等

2.数组的优缺点

    优点：存取速度快 ；

    缺点：事先必须知道数组的长度，插入删除元素很慢，空间通常是有限制的，需要大块连续的内存块。

3.连续存储数组示例

#include 
#include 	//包含了malloc函数 
#include  //包含了exit函数

//定义了一个数据类型，该数组名字叫做strcut Arr，该数据类型含有三个成员变量 
struct Arr
{
	int * pBase;	//存储的是数组的第一个元素的地址 
	int len;	//数据所能容纳的最大元素个数 
	int cnt; 	//当前数组有效元素的个数 
};

void init_arr(struct Arr * pArr, int lengt);	//分号不能省 
bool append_arr(struct Arr * pArr, int val);	//追加 
bool insert_arr(struct Arr * pArr, int pos, int val);	//插入 
bool delete_arr(struct Arr * pArr, int pos, int * pVal);	//删除
int get();
bool is_empty(struct Arr * pArr);
bool is_full(struct Arr * pArr);
void sort_arr(struct Arr * pArr);	//冒泡排序 
void show_arr(struct Arr * pArr);
void inversion_arr(struct Arr * pArr);	//倒置 

int main(void)
{
	struct Arr arr;
	int val;
	
	init_arr(&arr, 6);
	show_arr(&arr);
	append_arr(&arr, 1);
	append_arr(&arr, 2);
	append_arr(&arr, 3);
	append_arr(&arr, 4);
	append_arr(&arr, 5);
	insert_arr(&arr, 1, 77);
	show_arr(&arr);
	
	if (delete_arr(&arr, 1, &val))
	{
		printf("删除成功！\n");
		printf("您删除的元素是：%d\n", val);
	}
	else
		printf("删除失败！\n");
	show_arr(&arr);
	
	printf("倒置之后的数组是：");
	inversion_arr(&arr);
	show_arr(&arr);
	
	printf("冒泡排序之后得到的数组是：");
	sort_arr(&arr);
	show_arr(&arr);
	
	return 0;
} 

void init_arr(struct Arr * pArr, int length)
{
	pArr->pBase = (int *)malloc(sizeof(int) * length);
	if (NULL == pArr->pBase)
	{
		printf("动态内存分配失败！\n");
		exit(-1);	//终止整个程序 
	}
	else
	{
		pArr->len = length;
		pArr->cnt = 0;
	}
	return;
}

bool is_empty(struct Arr * pArr)
{
	if (0 == pArr->cnt)
		return true;
	else
		return false;
}

bool is_full(struct Arr * pArr)
{
	if (pArr->cnt == pArr->len)
		return true;
	else
		return false;
}

void show_arr(struct Arr * pArr)
{
	if ( is_empty(pArr) ){
		printf("数组为空！\n");
	}
	else
	{
		for (int i=0; i<pArr->cnt; i++)
			printf("%d ", pArr->pBase[i]);
		printf("\n"); 
	}
}

bool append_arr(struct Arr * pArr, int val)
{
	if ( is_full(pArr) )
		return false;
	else	//不满时追加
	{
		pArr->pBase[pArr->cnt] = val;
		(pArr->cnt)++;
		return true;
	} 
}

bool insert_arr(struct Arr * pArr, int pos, int val)
{
	int i;
	
	if (is_full(pArr))
		return false;
		
	if (pos<1 || pos>pArr->cnt+1)
		return false;
	for (i=pArr->cnt-1; i>=pos-1; i--)
	{
		pArr->pBase[i+1] = pArr->pBase[i];
	}
	pArr->pBase[pos-1] = val;
	(pArr->cnt)++;
	
	return true;
}

bool delete_arr(struct Arr * pArr, int pos, int * pVal)
{
	int i;
	
	if (is_empty(pArr))
		return false;
	else if(pos<1 || pos>pArr->cnt)
		return false;
	else
	{
		*pVal = pArr->pBase[pos-1];
		for(i=pos; i<pArr->cnt; i++)
		{
			pArr->pBase[i-1] = pArr->pBase[i];
		}
	(pArr->cnt)--;
	return true;
	}
}

void inversion_arr(struct Arr * pArr)
{
	int i = 0;
	int j = pArr->cnt-1;
	int t;
	
	while (i<j)
	{
		t = pArr->pBase[i];
		pArr->pBase[i] = pArr->pBase[j];
		pArr->pBase[j] = t;
		++i;
		--j;
	}
	return;
}

void sort_arr(struct Arr * pArr)
{
	int i, j, t;
	for (i=0; i<pArr->cnt; i++)
	{
		for (j=i+1; j<pArr->cnt; j++)
		{
			if (pArr->pBase[i] > pArr->pBase[j])
			{
				t = pArr->pBase[i];
				pArr->pBase[i] = pArr->pBase[j];
				pArr->pBase[j] = t;
			} 
		}
	}
}

（2）离散存储（链表）

1.定义

    n个节点离散分配；

    彼此通过指针相连；

    每个节点只有一个前驱节点，每个节点只有一个后续节点，首节点没有前驱节点，尾节点没有后续节点

2.专业术语

首节点：第一个有效节点

尾节点：最后一个有效节点

头结点：

    头结点的数据类型和首节点的数据类型一样；

    第一个有效节点 前 的那个节点；

    头结点并不存放有效数据；

    加头结点目的主要是为了方便对链表的 *** 作。

头指针：指向头结点的指针变量

尾指针：指向尾节点的指针变量

3.如果希望通过一个函数来对链表进行处理，我们至少需要接收链表的哪些参数？

    只需要一个参数：头指针

    因为我们通过头指针可以推算出链表的其他所有参数

4.分类

单链表

双链表：每一个节点都有两个指针域

循环链表：能通过任何一个节点找到其他所有的节点

非循环链表

5.优缺点

优点：插入删除元素效率高，不需要一个连续的很大的内存；

缺点：查找某个位置的元素效率低。

6.离散存储链表示例

 #include 
    #include 
    #include 
    
    typedef struct Node
    {
    	int data;	//数据域 
    	struct Node * pNext;	//指针域 
    }NODE, *PNODE;	//NODE等价于struct Node, PNODE等价于struct Node * 
    
    //函数声明 
    PNODE creat_list(void);
    void traverse_list(PNODE pHead);
    bool is_empty(PNODE);
    int length_list(PNODE);
    bool insert_list(PNODE, int, int);
    bool delete_list(PNODE, int, int *);
    void sort_list(PNODE);
    
    int main(void)
    {
    	int val; 
    	PNODE pHead = NULL;//等价于struct Node * pHead = NULL;
    	
    	pHead = creat_list();//创建一个非循环单链表，并将该链表的头结点的地址赋给pHead
    	traverse_list(pHead);
    	
    	if (is_empty(pHead))
    		printf("链表为空！\n");
    	else
    		printf("链表不为空！\n");
    		
    	int len = length_list(pHead);
    	printf("链表的长度是：%d\n", len);
    	
    	sort_list(pHead);
    	traverse_list(pHead);
    	
    	printf("插入一个元素后得到：\n"); 
    	insert_list(pHead, 2, 90);
    	traverse_list(pHead);
    	
    	if (delete_list(pHead, 2, &val))
    	{
    		printf("删除成功！\n");
    		printf("删除后得到的结果为：\n");
    		traverse_list(pHead);
    	}
    	else
    		printf("删除失败！\n");
    	
    	return 0;
    }
    
    PNODE creat_list(void)
    {
    	int len;//用来存放有效节点的个数
    	int i; 
    	int val;//用来临时存放用户输入的节点的值 
    	
    	PNODE pHead = (PNODE)malloc(sizeof(NODE));
    	PNODE pTail = pHead;
    	pTail->pNext = NULL;
    	 
    	if(NULL == pHead)
    	{
    		printf("分配失败，程序终止！\n");
    		exit(-1);
    	}
    	else
    	{
    		printf("请输入您要生成的链表节点的个数：len = ");
    		scanf("%d", &len);
    	
    		for (i=0; i<len; ++i)
    		{
    			printf("请输入第%d个节点的值:", i+1);
    			scanf("%d", &val);
    		
    			PNODE pNew = (PNODE)malloc(sizeof(NODE));
    			if (NULL == pNew)
    			{
    				printf("分配失败，程序终止！\n");
    				exit(-1);
    			}
    			else
    			{
    				pNew->data = val;
    				pTail->pNext = pNew;
    				pNew->pNext = NULL;
    				pTail = pNew;
    			}
    		}
    		return pHead;
    	}
    }
    
    void traverse_list(PNODE pHead)
    {
    	PNODE p = pHead->pNext;
    	while (p != NULL)
    	{
    		printf("%d ", p->data);
    		p = p->pNext;
    	}
    	printf("\n");
    }
    
    bool is_empty(PNODE pHead)
    {
    	if (pHead->pNext == NULL)
    		return true;
    	else
    		return false;
    }
    
    int length_list(PNODE pHead)
    {
    	PNODE p = pHead->pNext; 
    	int len = 0;
    	
    	while (p !=NULL)
    	{
    		++len;
    		p = p->pNext;
    	}
    	return len;
    }
    
    void sort_list(PNODE pHead)
    {
    	int i, j, t;
    	int len = length_list(pHead);
    	PNODE p, q;
    	
    	for (i=0, p=pHead->pNext; i<len-1; ++i, p=p->pNext)
    	{
    		for (j=i+1, q=p->pNext; j<len; ++j, q=q->pNext)
    		{
    			if (p->data > q->data)	//类似于数组中的a[i]>a[j] 
    			{
    				t = p->data;		//类似于数组中 t = a[i]; 
    				p->data = q->data;	//类似于数组中 a[i] = a[j]; 
    				q->data = t;		//类似于数组中 a[j] = t;
    			}
    		}
    	}
    	return;
    }
    
    //在pHead所指向链表的第pos个节点的前面插入一个新的节点，该节点的值是val，并且pos的值从1开始 
    bool insert_list(PNODE pHead, int pos, int val)
    {
    	int i = 0;
    	PNODE p = pHead;
    	
    	if (p == NULL || i>pos-1)
    		return false;
    	else
    	{
    		while (p!=NULL && i<pos-1)
    		{
    			p = p->pNext;
    			++i;
    		}
    		
    		PNODE pNew = (PNODE)malloc(sizeof(PNODE));
    		if (pNew == NULL)
    		{
    			printf("动态分配内存失败！\n");
    			exit(-1); 
    		}
    		else
    		{
    			pNew->data = val;
    			PNODE q = p->pNext;
    			p->pNext = pNew;
    			pNew->pNext = q;
    		}
    		return true;
    	}
    }
    
    bool delete_list(PNODE pHead, int pos, int * pVal)
    {
    	int i = 0;
    	PNODE p = pHead;
    	
    	if (p->pNext==NULL || i>pos-1)
    		return false;
    	else
    	{
    		while (p->pNext!=NULL && i<pos-1)
    		{
    			p = p->pNext;
    			++i;
    		}
    		PNODE q = p->pNext;
    		*pVal = p->data;
    		
    		//删除p节点后面的节点 
    		p->pNext = p->pNext->pNext;
    		free(q);
    		q = NULL;
    		
    		return true;
    	}
    }