数据结构线性表单链表的查找插入删除

《数据结构线性表单链表的查找插入删除》由会员分享，可在线阅读，更多相关《数据结构线性表单链表的查找插入删除（29页珍藏版）》请在装配图网上搜索。

1、实验报告课程名称姓名 学号 专业班级数据结构指导教师目录第二章线性表的查找、插入、删除 11.1顺序表的查找 11.2顺序表的插入 21.3顺序表的删除 4单链表的建立、插入、删除 62.1 单链表的建立（尾插法） 62.2 单链表的插入 82.3 单链表的删除 10第三章栈 143.1链栈 143.2 顺序栈 163.3 队列 183.4杨辉三角 20第四章串.234.1字符串的建立234.2顺序串的插入251.线性表的查找、插入、删除1.1 顺序表的查找程序：#include #include #include#define OK 1#define ERROR 0#define TRUE

2、1#define FALSE 0#define ElemType int#define MAXSIZE 100 /*此处的宏定义常量表示线性表可能达到的最大长度 */typedef structElemType elemMAXSIZE; /*线性表占用的数组空间*/int last;/*记录线性表中最后一个元素在数组elem中的位置(下标值)，空表为-1*/Seqlist;int Locate(Seqlist L,ElemType e)/*在顺序表L中查找与e相等的元素，若L。elemi=e，则找到该元素，并返回 i+1,若找不到，则返回-1*/ int i=0; /*i为扫描计数器，初值为0

3、，即从第一个元素开始比较*/ while (i=L.last)&(L.elemi!=e)/*顺序扫描表，直到找到值为e的元素，或扫描到表尾仍没找到*/ i+;if(i=L.last)return (i+1);/*若找到值为e的元素，则返回其序号*/elsereturn(-1); /*若没找到，则返回空序号*/void main()Seqlist l;int p，q，r;int i;prin tf(请输入线性标的长度:)； scanf(%d，&r);l.last=r-1;printf(请输入线性表的各元素值：n);for (i=0;i=l.last;i+) scanf(%d,&l.elemi);

4、prin tf(请输入要查找的元素值：n); scanf(%d,&q);p=Locate(l,q);if(p=-1)prin tf(在此线性表中没有该元素!n);elseprin tf(该素在线性表中的位置为:dn,p);执行结果：错误分析：在编写过程中，在编写主函数的时候有落下未编写的，导致运行过程中不 识别。1.2 顺序表的插入程序：#include #include /#include #define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define ElemType int#define MAXSIZE 100typedef

5、 structElemType elemMAXSIZE; int last;SeqList;/#include common.h/#include seqlist.h int InsList(SeqList *L,int i,ElemType e) int k; if(iL-last+2) printf(插入位置i值不合法); return(ERROR); if(L-last= MAXSIZE-1)prin tf(表已满无法插入)； return(ERROR); for(k=L-last;k=i-1;k-)L-elemk+1=L-elemk; L-elemi-1=e;L-last+; retu

6、rn(OK); void main()SeqList *l;int p,q,r;int i;l=(SeqList*)malloc(sizeof(SeqList);prin tf(请输入线性表的长度:)； scanf(%d,&r);l-last = r-1; prin tf(请输入线性表的各元素值:n);for(i=0; ilast; i+)scanf(%d,&l-elemi);prin tf(请输入要插入的位置：n);scanf(%d,&p);prin tf(请输入要插入的元素值：n);scanf(%d,&q);InsList(l,p,q);for(i=0; ilast; i+)printf(

7、%d ,l-elemi);执行结果：1.3 顺序表的删除程序：#include #include #include #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define ElemType int #define MAXSIZE 100 typedef structElemType elemMAXSIZE;int last;SeqList;int DelList(SeqList *L,int i,ElemType *e) int k;if(iL-last+1)prin tf(删除位置不合法!)； return(ER

8、ROR);*e = L-elemi-1；for(k=i； ilast； k+)L-elemk-1 = L-elemk；L-last-；return(OK)；void main()SeqList *l；int p,r；int *q；int i；l = (SeqList*)malloc(sizeof(SeqList)；q = (int*)malloc(sizeof(int)； prin tf(请输入线性表的长度:)； scanf(%d,&r)；l-last = r-1；prin tf(请输入线性表的各元素值:n);for(i=0； ilast； i+) scanf(%d,&l-elemi)；pri

9、n tf(请输入要删除的元素位置:n);scanf(%d,&p)；DelList(l,p,q);printf(删除的元素值为:dn, *q);执行结果：亘3 C:Users,.- X请输入线性表的长度：G 请输入线性炭的各元素值：12 25 12 65 15 65请输入要删除的元素位置：3囲除的元素值为：12Press any key to continue,2.单链表的建立、插入、删除2.1 单链表的建立(尾插法)程序：#include#include#define ERROR 0#define TRUE 1#define FALSE 0typedef char ElemType;typed

10、ef struct Node /*结点类型定义*/ElemType data;struct Node * next;Node, *LinkList; /* LinkList 为结构指针类型*/void ini t_linklis t( LinkList *l)/ *对单链表进行初始化*/*l=(LinkList)malloc(sizeof(Node);(*l)-next=NULL;void CreateFromTail(LinkList L)Node *r, *s;char c;int flag =1; /*设置一个标志，初值为，当输入$时，flag为，建表 结束*/r=L;/*r 指针动态指

11、向链表的当前表尾，以便于做尾插入，其初值指向头结点*/while(flag)/*循环输入表中元素值，将建立新结点s插入表尾*/c=getchar();if(c!=a)s=(Node*)malloc(sizeof(Node);s-data=c;r-next=s; r=s;elseflag=0;r-next二NULL;/*将最后一个结点的next链域置为空，表示链表的结束*/int main()LinkList l;Node *p;init_linklist(&l);printf(用尾插法建立单链表，请输入链表数据，以a结束!n);CreateFromTail(l);p = l-next;whil

12、e(p!=NULL)printf(%cn，p-data); p=p-next;return 0; 执行结果：1 nC:UsersMDesktopDcbug1 .exen X26 56 23 122akey to continue错误分析：在代码的时候忘记分号，导致运行错误；截图如下:Cjj 1 .ut)J - 1 errur(b) , 0 ufdriiiny(h)2.2 单链表的插入程序： #include common.h #include linklist.hint InsList(LinkList L,int i,ElemType e)/*在带头结点的单链表L中第i个位置插入值为e的新结

13、点s*/Node *pre,*s;int k;pre=L;k=0;/*从头开始，查找第i-1个结点*/while(pre!二NULL&knext;k=k+1;/*查找第i-1结点*/if(!pre)/*如当前位置pre为空表已找完还未数到第i个，说明插入位置不合理*/prin tf(“插入位置不合理!)；return ERROR;s=(Node*)malloc(sizeof(Node);/*申请一个新的结点 S */s-data二e;/*值e置入s的数据域*/s-next=pre-next;/*修改指针，完成插入操作*/pre-next=s;return OK;void main()LinkL

14、ist l;Node *p;int flag=0;int i;char c;init_linklist(&l);printf(请输入链表数据，以$结束!n);CreateFromTail(l);p = l-next; while(p!=NULL)printf(%cn，p-data); p=p-next;prin tf(请输入插入的位置和元素:n); scanf(%d，%c，&i，&c);printf(%cn，c); flag=InsList(l， i， c);if(flag)prin tf(插入操作成功！n);elseprin tf(插入操作失败！n); p = l-next;while(p!

15、=NULL)printf(%cn，p-data);p=p-next; 执行结果2.3 单链表的删除程序：#include #include #include #define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef char ElemType;typedef struct Node /*结点类型定义*/ElemType data;struct Node * next;Node, *LinkList; /* LinkList 为结构指针类型*/ void ini t_linklis t( LinkList *l)/ *对单链表

16、进行初始化*/*l=(LinkList)malloc(sizeof(Node);(*l)-next=NULL;void CreateFromTail(LinkList L)Node *r, *s;char c;int flag =1; /*设置一个标志，初值为 1，当输入$ 时，flag为0,建表结束*/r=L; /*r 指针动态指向链 表的当前表尾，以便于做尾插入，其初值指向头结点*/while(flag)/*循环输入表中元素值，将建立新结点s插入表尾*/c=getchar();if(c!=$)s=(Node*)malloc(sizeof(Node );s-data=c;r-next=s;r

17、=s;elseflag=0;r-next=NULL; /*将最后 一个结点的next链域置为空，表示链表的结束*/int DelList(LinkList L,int i,ElemType *e)/*在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量*e中 */Node *pre,*r;int k;pre=L;k=0;while(pre-next!二NULL & knext;k=k+1; /*查找第i-1个结点*/if(!(pre-next)/* 即 while 循环是因为 p-next二NULL 或 inext；pre-next二pre-next-next;/*修改指针，删除结点

18、 r*/*e = r-data；free(r);/*释放被删除的结点所占的内存空间*/printf(成功删除结点!n);/printf(被删除的元素是:cn, *e);return OK;void main()LinkList l;Node *p;int flag=0;int x;char*e;init_linklist(&l);printf(请输入链表数据，以$结束!n);CreateFromTail(l);p = l-next;while(p!=NULL)printf(%cn，p-data);p=p-next;printf(请输入要删除的元素位置：n); scanf(%d，&x);e =

19、(char*)malloc(sizeof(char); DelList(l，x，e);p = l-next;while(p!=NULL)printf(%c，p-data);p=p-next;printf(n); 执行结果 1 nC:UsersMDesktopDebug1 .exen X请输入链義数据,以$结束！12 23 4J121234请输入要刑除的元素位置：2成功删除结点！1 23 4Press any key to continue3.栈3.1 链栈程序：#include#include#define TRUE 1#define FALSE 0#define StackElementTy

20、pe inttypedef struct nodeStackElementType data;struct node *next;LinkStackNode;typedef LinkStackNode *LinkStack;int Push(LinkStack top,StackElementType x)LinkStackNode *temp;temp=(LinkStackNode *)malloc(sizeof(LinkStackNode); if(temp=NULL) return(FALSE);temp-data=x;temp-next=top-next;top-next=temp;

21、return(TRUE);int Pop(LinkStack top,StackElementType *x)LinkStackNode *temp; temp=top-next;if(temp=NULL) return(FALSE);top-next=temp-next;*x=temp-data;free(temp);return(TRUE);int main()LinkStackNode *top;top=(LinkStackNode *)malloc(sizeof(LinkStackNode); top-next=NULL;int flag=1;int a,x=0;printf(请输入链

22、表的各元素值(输入0代表结束)：n); while(flag)scanf(%d,&a);if(a!=0)Push(top,a);elseflag=0;while(top-next!=NULL)Pop(top,&x); printf(%dt,x);printf(n);return 0;执行结果:C:Uses秦越 Des kto pDe bug1. exenX请输入链表的各兀素值(输入0代表结束)：1 25 2 32 65 6600p606532225Press any key to conti nup_L3.2 顺序栈顺序栈进栈程序#include#include #include #defin

23、e stack_size 50typedef structint elemstack_size;int top;seqstack;void initstack(seqstack *s)s-top = -1;int push(seqstack *s, int x)if (s-top = stack_size - 1) return 0; s-top+;s-elems-top = x; return 1;void OutStack(seqstack *p)int i;if (p-toptop; i = 0; i-)printf(%d , p-elemi);int main()int a;int i

24、, r;seqstack *s;s = (seqstack*)malloc(sizeof(seqstack); initstack(s);prin tf(请输入长度:)；scanf(%d, &r);prin tf(请输入各元素值:n);for (i = 0； itop+;scanf(%d, &s-elemi);printf(请输入要进栈的值：)；scanf(%d, &a);push(s, a);OutStack(s);return 0;执行结果：4.队列顺序队列基本操作：#include#include#include#define MaxSize 20typedef int ElemType

25、;typedef structElemType dataMaxSize;int front,rear; /SqQueue;/顺序队列类型SqQueue的定义/初始化队列void InitQueue(SqQueue *&q)q=(SqQueue *)malloc(sizeof(SqQueue); q-front=q-rear=0;/销毁队列void ClearQueue(SqQueue *&q)free(q);/判断顺序队列是否为空void QueueEmpty(SqQueue *q)if(q-front=q-rear)printf(目前此顺序队列为空n);elseprin tf(目前此顺序队列

26、非空n);/进队列void enQueue( SqQueue *&q,ElemType e)if(q-rear+1)%MaxSize=q-front)prin tf(目前顺序队列已满了 n);elseq-rear=(q-rear+1)%MaxSize;q-dataq-rear=e;prin tf(“此次进队元素是:dn,e);/出队列void deQueue(SqQueue *&q,ElemType &e)if(q-front=q-rear)printf(目前此顺序队列为空n);else q-front=(q-front+1)%MaxSize;e=q-dataq-front;prin tf(“

27、此次出队元素是:dn,e);void main()SqQueue *q;int e;InitQueue(q);QueueEmpty(q);prin tf(请在此队头插入一个元素：n); scanf(%d,&e);while(e!=0)enQueue(q,e);printf(请继续此队头插入一个元素，或者停止插入队列元素，请按0n); scanf(%d,&e);QueueEmpty(q);int i;prin tf(如果想在此队尾出队一个元素，请按1n); scanf(%d,&i);while(i=1)deQueue(q,e);if(q-front=q-rear)prin tf(顺序队列的基本运

28、算操作到此结束了n); exit(0);elseprin tf(如果想在此队尾继续出队一个元素，请按1n);scanf(%d,&i);执行结果：5.杨辉三角(1)程序：#include #include #define TRUE 1 #define FALSE 0#define MAXSIZE 50 /*队列的最大长度*/ typedef structint elementMAXSIZE; /* 队列的元素空间*/int front; /*头指针指示器*/int rear; /*尾指针指示器*/SeqQueue;/*初始化操作*/void InitQueue(SeqQueue *Q)/*将*0

29、初始化为一个空的循环队列*/ Q-front=Q-rear=0;/*入队操作*/int EnterQueue(SeqQueue *Q, int x)/*将元素x入队*/ if(Q-rear+1)%MAXSIZE=Q-front) /*队列已经满了*/ return(FALSE);Q-elementQ-rear=x;Q-rear=(Q-rear+1)%MAXSIZE; /* 重新设置队尾指针*/ return(TRUE); /*操作成功*/*出队操作*/int DeleteQueue(SeqQueue *Q, int *x)/*删除队列的队头元素，用x返回其值*/ if(Q-front=Q-re

30、ar) /*队列为空*/return(FALSE); *x=Q-elementQ-front;Q-front=(Q-front+1)%MAXSIZE; /*重新设置队头指针*/ return(TRUE); /*操作成功*/int GetHead(SeqQueue *Q, int *x)/*提取队列的队头元素，用x返回其值*/ if(Q-front=Q-rear) /*队列为空*/return(FALSE); *x=Q-elementQ-front;return(TRUE); /*操作成功*/void YangHuiTriangle( )int n;int i;int temp;int x;in

31、t N;SeqQueue Q;InitQueue(&Q);EnterQueue(&Q,1); /* 第一行元素入队*/ pri ntf(请输入杨辉三角行数N:);scanf(%d,&N);for(n=2; n二N; n+)/*产生第n行元素并入队，同时打印第n-1行的元素*/EnterQueue(&Q,1);/*第n行的第一元素入队*/for(i=1;i5 74 6 9 81 4 n.-17 8 4 o 2 4 _b n - 8 6 n.-2 4 D 715550600553 7 2 3 9 1123 4 713 605 3 8 655 _b 81 2 n - 3 45 G -.11 2 91

32、01112136.串6.1 字符串的建立程序：#include #include #define MAXLEN 40#define MAXLEN 40typedef struct /*串结构定义*/ char chMAXLEN;int len;SString;void createstring(SString *s)int i,j;char c;prin tf(请输入要建立的串的长度:)； scanf(%d,&j);for(i=0； ichi = c;s-len = j;void output(SString *s)int i;for (i=0;ilen;i+)printf(%c ，s-chi

33、); printf(n);int StrEmpty(SString s)/*若串s为空则返回，否则返回*/ if (s.len=0)return(1);else return(0);int main()SString str2;int flag=0;printf (“建立字符串！n);createstring(&str2);flag=StrEmpty(str2);if(flag = 1)prin tf(字符串为空!);elseprin tf(字符串不为空！n); output(&str2);return 0;执行结果：c=XDoc-UAents aiLd. Setting：s.A(lAinis

34、t桌面ebu.g串-h 3 p p u- 个个个个个 -1 2 3 4 5 * Uss 建粉冏断商的为 苻要吕口 口串呂不 无入入入入入串 建请请请请请jl學hD t p V-p V-n&a s6.2 顺序串插入程序：#include #include #define MAXLEN 40typedef struct /*串结构定义*/ char chMAXLEN;int len;SString;void createstring(SString *s)int i,j; char c;prin tf(请输入要建立的串的长度:)； scanf(%d,&j);for(i=0； ichi = c; s

35、-len = j;void output(SString *s)int i;for (i=0;ilen;i+) printf(%c ，s-chi);printf(n); int StrInsert(SString *s， int pos， SString t) /*在串s中下标为pos的字符之前插入串t */int i;if (poss-len) /*插入位置不合法*/ return(0);if (s-len + t.len二MAXLEN) /*插入后串长 WMAXLEN */for (i=s-len + t.len-1;i=t.len + pos;i-) s-chi=s-chi-t.len;

36、for (i=0;ichi+pos=t.chi;s-len=s-len+t.len;elseif (pos+t.len二MAXLEN) /*插入后串长MAXLEN,但串t的字符序列可以 全部插入*/for (i=MAXLEN-1;it.len+pos-1;i-) s-chi=s-chi-t.len;for (i=0;ichi+pos=t.chi;s-len=MAXLEN;else /*插入后串长MAXLEN,并且串t的部分字符也要舍弃*/ for (i=0;ichi+pos=t.chi;s-len=MAXLEN; return(1); void main()SString *str1;SStr

37、ing str2;int i,j,k,pos;int flag=0;str1 = (SString *)malloc(sizeof(SString); str1-len = 0;printf (“建立字符串l:n); createstring(str1);printf (“建立字符串2:n); createstring(&str2);prin tf(请输入要插入的位置:); scanf(%d,&pos);flag=StrInsert(str1,pos,str2);if(flag = 0)prin tf(插入操作失败!)；elseprin tf(插入后串为：n); output(str1)；执行结果：匸： *C : Docimeitt s and Sett ings AdMi.nlst rat oDebug. exe8 siamhappy1:立 立 入： 建询抑时囱拥拥阿阿串建询旳阿阿插为m 雯吕吕吕吕吕吕吕吕符雯吕吕吕吕雾串 氏吹吹入入入IA宀|AlAlAlA!A后 a 建请请请请请请请请请建请请请请请性.eu Ery- .V T_J站个个个个血& 12 3 4 .pnasse rllp