博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
【数据结构】--章节2.3----线性表的链式表示和实现
阅读量：143 次
发布时间：2019-02-26

本文共 8253 字，大约阅读时间需要 27 分钟。

文章目录

注意：

这章需要注意一下，整个章节是这样的

  1. 第28页，给出了一个单链表存储结构
  2. 第29页到第31页：介绍了单链表的四个算法—2.8查找，2.9插入，2.10删除，2.11创建，2.12归并
  3. 第31页给出了静态单链表的存储结构
  4. 第32到34页：介绍了静态单链表的五个算法：2.13查找、2.14初始化、2.15malloc、2.16free、2.17一个例子
  5. 第35页，介绍了循环链表
  6. 第35页，介绍了双向链表存储结构
  7. 第36页，算法2.18介绍了双向循环链表的插入算法，2.19介绍了删除算法
  8. 最终在第37页，重新给出了线性链表的类型定义以及重写了两个算法，2.20插入、2.21归并
  9. 39页到43页展示了如何用线性表表示一元多项式以及计算一元多项式

所以，其实这章是个讨论的过程，最初我们给出一个链表的定义，并且实践了他的各种操作，我们会发现这个结构存在一些弊端，在做不同行为的时候，操作不统一，为了统一操作，最终我们根据需求，重新定义了链表的存储结构，统一了各项操作。

本文内容与课本此章节的顺序并不一一对应。

存储结构

在这里插入图片描述

最终的这个存储结构采用头指针---->头结点---->数据头结点---->数据结点的模式

typedef struct LDataNode{
   	int x;	struct LDataNode *next;//结点指针}LDataNode;typedef struct LHeadNode{
   	LDataNode *next; //头	LDataNode *tail; //尾}LHeadNode,*LinkList;

在这里插入图片描述

很多同学不太理解，为什么这个存储结构要一遍一遍的改，很多个版本，其实是为了统一化操作。

如果你也不清楚什么叫统一操作，那我举个例子。
我们最终采用的这个结构，你会发现，头结点由于存放关于链表的信息，所以不存放数据，但是还有一个数据节点也没存东西，为什么不存呢，岂不是浪费了？这里就体现了统一操作的思想。
你想一下，如果第一个位置也存放数据，那么当链表为空的时候，头尾指针没地方指，所以要置为空，当来了第一个元素，链表不为空了，那头尾指针都要指向这个元素，而来了第二个元素的时候，我们只需要更新尾指针就好了，不用更新头指针了。发现了没，同样是添加元素，第一个和其他元素，操作不一样，也就意味着我们要特殊判断，而我们牺牲第一个结点，不存数据，就把操作统一化了，你就会发现，不论添加第几个元素，操作都一样。
不止这一个例子，还有别的类似的操作，总之就记住，我们优化存储结构，都是为了操作统一化。

ps：当然了，并没有规定你写链表必须写这样的结构。如果你完全理解了这几个结构的优缺点，你就可以灵活运用了，根据实际情况，选择最合适的结构。

下面我写的算法，都基于本文给出的存储结构来写！，（而非第28页的存储结构）

链表的初始化

int InitList(LinkList *head){
   //初始化链表	*head =(LinkList)malloc(sizeof(LHeadNode));	LDataNode *vhNode =(LDataNode *)malloc(sizeof(LDataNode));	if(*head==NULL||vhNode==NULL){
   		return -1;//申请失败	}	vhNode->next=NULL;	(*head)->next=vhNode;	(*head)->tail=vhNode;	return 0;}

在链表末尾添加元素

由于头结点的指针域中有了尾指针，所以使我们在链表末尾添加元素变得很容易。

int AddList(LinkList *head,int a){
   //链表末尾添加元素    LDataNode *vhNode =(LDataNode *)malloc(sizeof(LDataNode));    if(vhNode==NULL){
   		return -1;//申请失败	}	vhNode->x=a;	vhNode->next=NULL;	(*head)->tail->next=vhNode;//挂到末尾	(*head)->tail=vhNode;//尾指针更新	return 0;}

遍历链表

注意，遍历的时候我们传的参数，与其他操作不一样，由于遍历只用访问元素，不需要对结点做出改变，所以不需要双重指针！单重指针就够了。

int LTraverse(LinkList head){
   //遍历输出链表	LDataNode *p=head->next->next;//注意 第一个数据节点不存数据 所以 第二个才是开头	while(p){
   		printf("%d ",p->x);		p=p->next;	}	printf("\n");	return 0;}

删除链表中指定位置元素

/******author:  1900language: C******/#include
   
    #include
    
     #include
     
      typedef struct LDataNode{
   	int x;	struct LDataNode *next;}LDataNode;typedef struct LHeadNode{
   	LDataNode *next;	LDataNode *tail;}LHeadNode,*LinkList;int InitList(LinkList *head){
   //初始化链表	*head =(LinkList)malloc(sizeof(LHeadNode));	LDataNode *vhNode =(LDataNode *)malloc(sizeof(LDataNode));	if(*head==NULL||vhNode==NULL){
   		return -1;//申请失败	}	vhNode->next=NULL;	(*head)->next=vhNode;	(*head)->tail=vhNode;	return 0;}int AddList(LinkList *head,int a){
   //链表末尾添加元素    LDataNode *vhNode =(LDataNode *)malloc(sizeof(LDataNode));    if(vhNode==NULL){
   		return -1;//申请失败	}	vhNode->x=a;	vhNode->next=NULL;	(*head)->tail->next=vhNode;//挂到末尾	(*head)->tail=vhNode;//尾指针更新	return 0;}int LTraverse(LinkList head){
   //遍历输出链表	LDataNode *p=head->next->next;	while(p){
   		printf("%d ",p->x);		p=p->next;	}	printf("\n");	return 0;}//删除链表中第i个元素int DeleteList(LinkList *head,int i,int *e){
       if(i<1) return -1;//不合法    int num=1;    LDataNode *p=(*head)->next;//指向第0个结点 现在p->next就是第一个    while(num!=i&&p->next!=NULL){
           p=p->next;        num++;    }    if(p->next==NULL)return -1;//不合法    *e=p->next->x;    p->next=p->next->next;//删除    return 0;}int main(){
   	LinkList head;//初始化一个链表	InitList(&head);	//赋值为1-10	for(int i=1;i<=10;i++){
           AddList(&head,i);	}	LTraverse(head);//遍历链表    int e;    DeleteList(&head,3,&e);//删除第三个元素    printf("%d\n",e);//打印被删除的元素    LTraverse(head);//遍历删除后的链表}

删除链表中值为e的元素

与删除第i个元素类似，循环条件改改就行了。

无论是删除值为e的元素还是删除第i个元素，首先就是要找到它，所以，关于在链表中查找元素的算法，我就不单独写了。

//删除链表中值为e的元素int DeletList_value(LinkList *head,int e){
       LDataNode *p=(*head)->next;//指向第0个结点 现在p->next就是第一个    while(p->next->x!=e){
           p=p->next;    }    if(p->next==NULL)return -1;//没找到    p->next=p->next->next;//删除    return 0;}

在第i个元素前面插入元素

注意，这里的在第i个元素前面插入元素e，不包括在末尾插入元素的操作。

//第i个元素前面插入元素eint InsertList(LinkList *head,int i,int e){
       if(i<1) return -1;//不合法    int num=1;    LDataNode *p=(*head)->next;//指向第0个结点 现在p->next就是第一个    while(num!=i&&p->next!=NULL){
           p=p->next;        num++;    }    if(p->next==NULL)return -1;//不合法    LDataNode *vhNode =(LDataNode *)malloc(sizeof(LDataNode));    if(vhNode==NULL){
   		return -1;//申请失败	}	vhNode->x=e;	vhNode->next=p->next;    p->next=vhNode;    return 0;}

循环链表

写法不唯一！

循环链表与普通链表的区别只是最后一个元素指向头结点，在判断结束的时候判断是否指向头结点。
这里给出其初始化函数。

int InitList(LinkList *head){
   	*head =(LinkList)malloc(sizeof(LHeadNode));	LDataNode *vhNode =(LDataNode *)malloc(sizeof(LDataNode));	if(*head==NULL||vhNode==NULL){
   		return -1;	}	vhNode->next=(*head)->next;//最后一个元素指向开头	(*head)->next=vhNode;	(*head)->tail=vhNode;	return 0;}

双向链表

双向链表与单链表相比，就是增加了前驱指针，方便向前寻找前驱。

下面这个例子，实现了通过前驱指针倒着遍历整个链表

/******author:  1900language: C******/#include
   
    #include
    
     #include
     
      typedef struct LDataNode{
   	int x;	struct LDataNode *next;	struct LDataNode *pre;}LDataNode;typedef struct LHeadNode{
   	LDataNode *next;	LDataNode *tail;}LHeadNode,*LinkList;int InitList(LinkList *head){
   	*head =(LinkList)malloc(sizeof(LHeadNode));	LDataNode *vhNode =(LDataNode *)malloc(sizeof(LDataNode));	if(*head==NULL||vhNode==NULL){
   		return -1;	}	vhNode->next=NULL;	vhNode->pre=NULL;//首结点前驱为空 也可以置为他自己 根据需要来设置	(*head)->next=vhNode;	(*head)->tail=vhNode;	return 0;}int AddList(LinkList *head,int a){
   //链表末尾添加元素    LDataNode *vhNode =(LDataNode *)malloc(sizeof(LDataNode));    if(vhNode==NULL){
   		return -1;	}	vhNode->x=a;	vhNode->next=NULL;	vhNode->pre=(*head)->tail;//设置前驱	(*head)->tail->next=vhNode;	(*head)->tail=vhNode;	return 0;}int d_LTraverse(LinkList head){
   //利用前驱指针遍历链表	LDataNode *p=head->tail;	while(p->pre!=NULL){
   		printf("%d ",p->x);		p=p->pre;	}	printf("\n");	return 0;}int LTraverse(LinkList head){
   //遍历输出链表	LDataNode *p=head->next->next;	while(p){
   		printf("%d ",p->x);		p=p->next;	}	printf("\n");	return 0;}int main(){
   	LinkList head;//初始化一个链表	InitList(&head);	//赋值为1-10	for(int i=1;i<=10;i++){
           AddList(&head,i);	}	LTraverse(head);//遍历链表    d_LTraverse(head);//利用前驱指针 遍历链表}

使用链表实现一元多项式的加法运算

我们用链表表示多项式的时候，是存下每一项的系数和指数

做加法时候，指数相同，直接把系数相加就好了，指数不同不能加。
下面给一个实现例子。
用链表实现这两个多项式相加。
在这里插入图片描述
在这里插入图片描述

/******author:  1900language: C需求：两个一元多项式做加法要求：每个多项式有五项，输入每一项的系数和指数，且按照指数升序输入，最终打印相加后的多项式各项系数和指数。******/#include
   
    #include
    
     #include
     
      typedef struct LDataNode{
   	int x;//系数	int z;//指数	struct LDataNode *next;}LDataNode;typedef struct LHeadNode{
   	LDataNode *next;	LDataNode *tail;}LHeadNode,*LinkList;int InitList(LinkList *head){
   //初始化链表	*head =(LinkList)malloc(sizeof(LHeadNode));	LDataNode *vhNode =(LDataNode *)malloc(sizeof(LDataNode));	if(*head==NULL||vhNode==NULL){
   		return -1;//申请失败	}	vhNode->next=NULL;	(*head)->next=vhNode;	(*head)->tail=vhNode;	return 0;}int AddList(LinkList *head,int a1,int a2){
   //链表末尾添加元素    LDataNode *vhNode =(LDataNode *)malloc(sizeof(LDataNode));    if(vhNode==NULL){
   		return -1;	}	vhNode->x=a1;//系数	vhNode->z=a2;//指数	vhNode->next=NULL;	(*head)->tail->next=vhNode;	(*head)->tail=vhNode;	return 0;}int LTraverse(LinkList head){
   	LDataNode *p=head->next->next;	while(p){
   		printf("系数:%d  指数: %d\n",p->x,p->z);		p=p->next;	}	printf("\n");	return 0;}Add_LinkList(LinkList *H1,LinkList *H2,LinkList *H3){
       LDataNode *p=(*H1)->next->next;    LDataNode *q=(*H2)->next->next;    while(q&&p){
           if(q->z==p->z){
               AddList(H3,q->x+p->x,q->z);            q=q->next;p=p->next;        }        else if(q->z>p->z){
               AddList(H3,q->x,q->z);            q=q->next;        }        else if(q->z
      
       z){
               AddList(H3,p->x,p->z);            p=p->next;        }    }    while(q){
          AddList(H3,q->x,q->z);       q=q->next;    }    while(p){
           AddList(H3,p->x,p->z);        p=p->next;    }    return 0;}int main(){
   	LinkList H1,H2,H3;	InitList(&H1);	InitList(&H2);	InitList(&H3);	int T1=5,T2=5,a1,a2;	while(T1--){
      //输入第一个多项式        scanf("%d%d",&a1,&a2);        AddList(&H1,a1,a2);	}    while(T2--){
      //输入第二个多项式        scanf("%d%d",&a1,&a2);        AddList(&H2,a1,a2);	}	//LTraverse(H1);	//LTraverse(H2);    Add_LinkList(&H1,&H2,&H3);//做加法运算    LTraverse(H3);//打印最终结果}

转载地址：http://evuf.baihongyu.com/

你可能感兴趣的文章
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2025-03-13 12:20:25   当前IP: 3.144.147.66   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我