数据结构-----第二章线性表

忘是亡心i 2022-09-19 15:26 200阅读 0赞

**注意：下列作业请于9月12日周三下午上课前交**

**1、** **链接存储方法**

▲链接方式存储的线性表简称为链表（Linked List）。  
▲链表的具体存储表示为：  
　　① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）  
　　② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系， ▲在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）  
▲ 注意：   
 　　链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。

**7 C** **/C++** **完整代码实现** **-------(** **不带头结点** **)** **单链表上实现的基本运算**

**/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\***   
 **Copyright (C)  
 FileName: S\_LinkList.cpp  
 Author: Luqing Date:2006/4/11  
 Description: // The basic operations of S\_LinkList (0-n)   
 Version: // v1.0  
 Function List: //Del\_LinkList** **,**  **Insert\_LinkList**   
**\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/**

**\#include <stdio.h>**

**\#include <malloc.h>**

**typedef char ElemType;**

**typedef struct Node**

**\{**

**ElemType data;**

**struct Node \*next;**

**\}LNode,\*LinkList;**

**LinkList CreatListF()**

**\{//** **用头插法建立单链表**

**ElemType ch;**

**LinkList H=NULL; //** **链表头指针开始为空**

**LNode \*p; //** **工作指针**

**ch=getchar(); //** **读入第1** **个字符**

**if(ch=='/n')**

**printf("** **你已经退出了!!/n");**

**else\{**

**while(ch!='/n')\{**

**p=(LNode \*)malloc(sizeof(LNode));//** **生成新结点**

**p->data=ch; //** **将读入的数据放入新结点的数据域中**

**p->next=H;**

**H=p;**

**ch=getchar(); //** **读入下一字符**

**\}**

**return H;**

**\}**

**LinkList CreatListR()**

**\{//** **用尾插法建立单链表**

**ElemType ch;**

**LinkList H=NULL;//** **链表头指针开始为空**

**LNode \*P,\*r=H; //** **工作指针p** **，指针r** **用于指向链表中的尾结点**

**ch=getchar();**

**if(ch=='/n')**

**printf("** **你已经退出了!!/n");**

**else\{**

**while(ch!='/n')\{**

**P=(LNode \*)malloc(sizeof(LNode));//** **生成新结点**

**P->data=ch; //** **将读入的数据放入新结点的数据域中**

**P->next=NULL;**

**if(H==NULL)**

**H=P;**

**else**

**r->next=P;**

**r=P;**

**ch=getchar();**

**\}**

**return H;**

**\}**

**int length\_LinkList(LinkList H)**

**\{**

**int n=1;**

**struct Node \*p=H;**

**if(p==NULL) return -1;**

**else\{**

**while (p->next!=NULL)**

**\{**

**n++;**

**p=p->next;**

**\}**

**return(n);**

**\}**

**int Locate\_LinkList(struct Node \*H,ElemType x)**

**\{**

**int n=0;**

**struct Node \*p=H;**

**while (p!=NULL&&p->data!=x) //** **查找data** **域为x** **的第一个结点**

**\{**

**p=p->next;**

**n++;**

**\}**

**if(p==NULL) return -1;**

**else return n;**

**\}**

**ElemType Get\_LinkList(struct Node \*H,int i)**

**\{**

**struct Node \*p=H;**

**int j=0;**

**while (p!=NULL && j<i) //** **查找第i** **个结点**

**\{**

**p=p->next;**

**j++;**

**\}**

**if(p!=NULL &&j==i) return p->data;**

**else return '/n';**

**\}**

**struct Node \* GetPtr\_LinkList(struct Node \*H,int i)**

**\{**

**struct Node \*p=H;**

**int j=-1;**

**while (p!=NULL && j<i) //** **查找第i** **个结点**

**\{**

**p=p->next;**

**j++;**

**\}**

**if(j==i) return p;**

**else return NULL;**

**\}**

**void Insert\_LinkList(struct Node \*H,ElemType x,int i)**

**\{**

**int j=1,k=i;**

**struct Node \*S,\*P;**

**P=GetPtr\_LinkList(H,i-1); //** **后插入步1** **，前插入则为P=Get\_LinkList(H,i);**

**if(P ==NULL) \{**

**printf("no elements found!/n");**

**\}**

**else\{**

**S =(struct Node \*)malloc(sizeof(struct Node)); //** **建立要插入的结点s**

**S ->data=x;**

**S ->next= P ->next;**

**P ->next= S;**

**\}**

**void Del\_LinkList(struct Node \*H,int i)**

**\{**

**struct Node \*P,\*r;**

**P=GetPtr\_LinkList(H,i-1);**

**if(P==NULL)**

**printf("i-1 no elements found!/n");**

**else if(P->next==NULL)**

**printf("the i node is not exist/n");**

**else\{**

**r=P->next;**

**P->next=r->next;**

**free(r);**

**\}**

**void display(struct Node \*H)**

**\{**

**struct Node \*p;**

**p=H;**

**printf("** **单链表显示:");**

**if (p==NULL)**

**printf("** **链表为空!/n");**

**else**

**\{**

**while (p->next!=NULL) //** **链表存在一个以上的结点时**

**\{**

**printf("%c** **→",p->data);**

**p=p->next;**

**\}**

**printf("%c",p->data); //** **显示存在一个结点或显示最后一个结点**

**\}**

**printf("/n");**

**\}**

**int main()**

**\{**

**struct Node \*H;**

**printf("** **提示**  **：回车表示输入完毕!/n");**

**printf("input the chars :/n");**

**H=CreatListR();**

**//H=CreatListF();**

**display(H);**

**printf("/n** **单链表长度=%d/n",length\_LinkList(H));**

**printf("** **值:%c**  **位置:%d/n",'a',Locate\_LinkList(H,'a'));**

**printf("** **位置:%d**  **值:%c/n",0,Get\_LinkList(H,0));**

**printf("** **位置:%d**  **值:%c/n",2,Get\_LinkList(H,2));**

**display(H);**

**/\*** **下列不能正确执行，显示出该插入方法的局限性\*/**

**//printf("** **插入第0** **个结点:");**

**//Insert\_LinkList(H,'L',0);**

**//display(H);**

**printf("** **插入第1** **个结点:");**

**Insert\_LinkList(H,'u',1);**

**display(H);**

**printf("** **插入第2** **个结点:");**

**Insert\_LinkList(H,'e',2);**

**display(H);**

**/\*** **下列不能正确执行，显示出该插入方法的局限性\*/**

**//printf("** **删除第0** **个结点:");**

**//Del\_LinkList(H,0);**

**//display(H);**

**printf("** **删除第1** **个结点:");**

**Del\_LinkList(H,1);**

**display(H);**

**printf("** **删除第2** **个结点:");**

**Del\_LinkList(H,2);**

**display(H);**

**return 0;**

**\}**

数据结构-----第二章线性表

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关数据结构第二章线性表相关习题

相关数据结构第二章线性表

相关数据结构：第二章线性表

相关数据结构---第二章_线性表-顺序表的实现

相关《数据结构》复习——第二章线性表

相关数据结构习题——第二章线性表

相关数据结构-----第二章线性表

相关数据结构第二章线性表

相关数据结构学习笔记第二章线性表

相关数据结构第二章线性表作业