数据结构(三)

淡淡的烟草味﹌ 2022-08-20 10:09 118阅读 0赞

接着链表，删除一个结点：

方法一: p->pNext=p->pNext->pNext;

方法二: r=p->pNext; p->pNext=p->pNext->pNext;free(r)

很显然，方法一虽然删除了p的下一个结点，可是被删结点的内存还标记着使用状态，系统并没有回收，造成内存泄漏。方法二是方法一的解决方法。

补充：线性结构：能用一根线把所有结点串起来，数组，链表是典型的线性结构，树和图不是。

算法：狭义的算法与数据的存储方式密切相关。

广义的算法与数据的存储方式无关。（也就是泛型思想）

泛型：利用某种技术达到的效果就是：不同的存储方式，执行的操作是一样的。Java的泛型不只是操作一样。

链表的算法：

#include<stdio.h>
    #include<malloc.h>
    #include<stdlib.h>
    
    typedef struct Node
    {
    	int data;//数据域
    	struct Node * pNext;//指针域
    }NODE,*PNODE;
    //函数声明
    PNODE create_list(void);//创建链表
    void traverse_list(PNODE pHead);//遍历链表
    bool is_empty(PNODE pHead);
    int length_list(PNODE pHead);
    bool insert_list(PNODE pHead,int pos,int val);
    bool delete_list(PNODE pHead,int pos,int * pVal);
    void sort_list(PNODE pHead);
    int main(void)
    {
    	PNODE pHead = NULL;
    	pHead = create_list();
    	int len;
    	int val;
    	traverse_list(pHead);
    	if(is_empty(pHead))
    	{
    		printf("链表为空!\n");
    	}
    	else
    	{
    		printf("链表不为空!\n");
    		if(delete_list(pHead,3,&val))
    		{
    			printf("删除%d成功!\n",val);
    			if(insert_list(pHead,2,77))
    			{
    				printf("添加成功!\n");
    			}
    			else
    			{
    				printf("添加不成功!");
    			}
    		}
    		else
    		{
    			printf("删除不成功!\n");
    		}
    	}
    	len=length_list(pHead);
    	printf("链表长度是%d\n",len);
    	printf("**********排序后\n");
    	sort_list(pHead);
        traverse_list(pHead);
    	return 0;
    }
    PNODE create_list(void)
    {
    	int len;//用来存放有效结点的个数
    	int i;
    	int val;
    	PNODE pHead = (PNODE)malloc(sizeof(NODE));
    	if(NULL == pHead)
    	{
    		printf("分配失败，程序终止!\n");
    		exit(-1);
    	}
    	PNODE pTail=pHead;
    	pTail->pNext=NULL;
    	printf("请输入您需要生成链表的结点的个数:len=\n");
        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);
    		}
    		pNew->data=val;
    		pNew->pNext=NULL;
    		pTail->pNext=pNew;
    		pTail=pNew;
    	}
    	return pHead;
    }
    void traverse_list(PNODE pHead)
    {
    	printf("******************\n");
    	PNODE p=pHead->pNext;
    	while(p != NULL)
    	{
    		//printf("******************");
    		printf("%d  ",p->data);
    		p=p->pNext;
    	}
    	printf("\n");
    	return;
    }
    bool is_empty(PNODE pHead)
    {
    	if(NULL == pHead->pNext)
    	{
    		return true;
    	}
    	else
    	{
    		return false;
    	}
    }
    int length_list(PNODE pHead)
    {
    	PNODE p=pHead->pNext;
    	int len=0;
    	while(NULL != p)
    	{
    		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[j]=a[i]
    				q->data=t;//类似于数组的a[j]=t
    			}
    		}
    	}
    	return;
    }
    bool insert_list(PNODE pHead,int pos,int val)
    {
    	int i=0;
    	PNODE p=pHead;
    	while(NULL != p && i<pos-1)
    	{
    		p=p->pNext;
    		i++;
    	}
    	if(i>pos-1||p == NULL)
    	{
    		return false;
    	}
    	PNODE pNew=(PNODE)malloc(sizeof(NODE));
    	if(NULL==pNew)
    	{
    		printf("动态分配内存失败!\n");
    		exit(-1);
    	}
    	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;
    	while(NULL != p && i<pos-1)
    	{
    		p=p->pNext;
    		i++;
    	}
    	if(i>pos-1||p == NULL)
    	{
    		return false;
    	}
    	PNODE q=p->pNext;
    	*pVal=q->data;
    	p->pNext=p->pNext->pNext;
    	free(q);
    	q=NULL;
    	return true;
    }

![Center][]

再复习一下数据结构：

狭义：

数据结构是专门研究数据存储的问题。

数据的存储包含两个方面：个体的存储 \+ 个体关系的存储。

广义：

数据结构既包含数据的存储也包含数据的操作。

对存储数据的操作就是算法。

数据的存储结构：

线性：

连续存储\[数组\]

优点：存取速度快