数据结构线性表单链表的查找插入删除.docx
- 文档编号:18113456
- 上传时间:2023-08-13
- 格式:DOCX
- 页数:38
- 大小:251.02KB
数据结构线性表单链表的查找插入删除.docx
《数据结构线性表单链表的查找插入删除.docx》由会员分享,可在线阅读,更多相关《数据结构线性表单链表的查找插入删除.docx(38页珍藏版)》请在冰点文库上搜索。
数据结构线性表单链表的查找插入删除
实验报告
课程名称
数据结构
姓名
学号
专业班级
指导教师
第四章串..…………………………………………………………23
4.1字符串的建立...................................23
4.2顺序串的插入...................................25
1.线性表的查找、插入、删除
1.1顺序表的查找
程序:
#include
#include
#include
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
#defineElemTypeint
#defineMAXSIZE100/*此处的宏定义常量表示线性表可能达到的最大长度*/
typedefstruct
{
ElemTypeelem[MAXSIZE];/*线性表占用的数组空间*/
intlast;/*记录线性表中最后一个元素在数组elem[]中的位置(下标值),空表为-1*/
}Seqlist;
intLocate(SeqlistL,ElemTypee)
/*在顺序表L中查找与e相等的元素,若L。
elem[i]=e,则找到该元素,并返回i+1,若找不到,则返回-1*/
{inti=0;/*i为扫描计数器,初值为0,即从第一个元素开始比较*/
while((i<=L.last)&&(L.elem[i]!
=e))
/*顺序扫描表,直到找到值为e的元素,或扫描到表尾仍没找到*/
i++;
if(i<=L.last)
return(i+1);/*若找到值为e的元素,则返回其序号*/
else
return(-1);/*若没找到,则返回空序号*/
}
voidmain()
{
Seqlistl;
intp,q,r;
inti;
printf("请输入线性标的长度:
");
scanf("%d",&r);
l.last=r-1;
printf("请输入线性表的各元素值:
\n");
for(i=0;i<=l.last;i++)
{
scanf("%d",&l.elem[i]);
}
printf("请输入要查找的元素值:
\n");
scanf("%d",&q);
p=Locate(l,q);
if(p==-1)
printf("在此线性表中没有该元素!
\n");
else
printf("该素在线性表中的位置为:
%d\n",p);
}
执行结果:
错误分析:
在编写过程中,在编写主函数的时候有落下未编写的,导致运行过程中不识别。
1.2顺序表的插入
程序:
#include
#include
//#include
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
#defineElemTypeint
#defineMAXSIZE100
typedefstruct
{
ElemTypeelem[MAXSIZE];
intlast;
}SeqList;
//#include"common.h"
//#include"seqlist.h"
intInsList(SeqList*L,inti,ElemTypee)
{
intk;
if((i<1)||(i>L->last+2))
{
printf("插入位置i值不合法");
return(ERROR);
}
if(L->last>=MAXSIZE-1)
{
printf("表已满无法插入");
return(ERROR);
}
for(k=L->last;k>=i-1;k--)
L->elem[k+1]=L->elem[k];
L->elem[i-1]=e;
L->last++;
return(OK);
}
voidmain()
{
SeqList*l;
intp,q,r;
inti;
l=(SeqList*)malloc(sizeof(SeqList));
printf("请输入线性表的长度:
");
scanf("%d",&r);
l->last=r-1;
printf("请输入线性表的各元素值:
\n");
for(i=0;i<=l->last;i++)
{
scanf("%d",&l->elem[i]);
}
printf("请输入要插入的位置:
\n");
scanf("%d",&p);
printf("请输入要插入的元素值:
\n");
scanf("%d",&q);
InsList(l,p,q);
for(i=0;i<=l->last;i++)
{
printf("%d",l->elem[i]);
}
}
执行结果:
1.3顺序表的删除
程序:
#include
#include
#include
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
#defineElemTypeint
#defineMAXSIZE100
typedefstruct
{
ElemTypeelem[MAXSIZE];
intlast;
}SeqList;
intDelList(SeqList*L,inti,ElemType*e)
{
intk;
if((i<1)||(i>L->last+1))
{
printf("删除位置不合法!
");
return(ERROR);
}
*e=L->elem[i-1];
for(k=i;i<=L->last;k++)
L->elem[k-1]=L->elem[k];
L->last--;
return(OK);
}
voidmain()
{
SeqList*l;
intp,r;
int*q;
inti;
l=(SeqList*)malloc(sizeof(SeqList));
q=(int*)malloc(sizeof(int));
printf("请输入线性表的长度:
");
scanf("%d",&r);
l->last=r-1;
printf("请输入线性表的各元素值:
\n");
for(i=0;i<=l->last;i++)
{
scanf("%d",&l->elem[i]);
}
printf("请输入要删除的元素位置:
\n");
scanf("%d",&p);
DelList(l,p,q);
printf("删除的元素值为:
%d\n",*q);
}
执行结果:
2.单链表的建立、插入、删除
2.1单链表的建立(尾插法)
程序:
#include
#include
#defineERROR0
#defineTRUE1
#defineFALSE0
typedefcharElemType;
typedefstructNode/*结点类型定义*/
{
ElemTypedata;
structNode*next;
}Node,*LinkList;/*LinkList为结构指针类型*/
voidinit_linklist(LinkList*l)/*对单链表进行初始化*/
{
*l=(LinkList)malloc(sizeof(Node));
(*l)->next=NULL;
}
voidCreateFromTail(LinkListL)
{
Node*r,*s;
charc;
intflag=1;/*设置一个标志,初值为,当输入"$"时,flag为,建表结束*/
r=L;/*r指针动态指向链表的当前表尾,以便于做尾插入,其初值指向头结点*/
while(flag)/*循环输入表中元素值,将建立新结点s插入表尾*/
{
c=getchar();
if(c!
='a')
{
s=(Node*)malloc(sizeof(Node));
s->data=c;
r->next=s;
r=s;
}
else
{
flag=0;
r->next=NULL;/*将最后一个结点的next链域置为空,表示链表的结束*/
}
}
}
intmain()
{
LinkListl;
Node*p;
init_linklist(&l);
printf("用尾插法建立单链表,请输入链表数据,以a结束!
\n");
CreateFromTail(l);
p=l->next;
while(p!
=NULL)
{
printf("%c\n",p->data);
p=p->next;
}
return0;
}
执行结果:
错误分析:
在代码的时候忘记分号,导致运行错误;截图如下:
2.2单链表的插入
程序:
#include"common.h"
#include"linklist.h"
intInsList(LinkListL,inti,ElemTypee)
/*在带头结点的单链表L中第i个位置插入值为e的新结点s*/
{
Node*pre,*s;
intk;
pre=L;
k=0;/*从"头"开始,查找第i-1个结点*/
while(pre!
=NULL&&k { pre=pre->next; k=k+1; }/*查找第i-1结点*/ if(! pre)/*如当前位置pre为空表已找完还未数到第i个,说明插入位置不合理*/ { printf("插入位置不合理! "); returnERROR; } s=(Node*)malloc(sizeof(Node));/*申请一个新的结点S*/ s->data=e;/*值e置入s的数据域*/ s->next=pre->next;/*修改指针,完成插入操作*/ pre->next=s; returnOK; } voidmain() { LinkListl; Node*p; intflag=0; inti; charc; init_linklist(&l); printf("请输入链表数据,以$结束! \n"); CreateFromTail(l); p=l->next; while(p! =NULL) { printf("%c\n",p->data); p=p->next; } printf("请输入插入的位置和元素: \n"); scanf("%d,%c",&i,&c); printf("%c\n",c); flag=InsList(l,i,c); if(flag) printf("插入操作成功! \n"); else printf("插入操作失败! \n"); p=l->next; while(p! =NULL) { printf("%c\n",p->data); p=p->next; } } 执行结果: 2.3单链表的删除 程序: #include #include #include #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef char ElemType; typedef struct Node /*结点类型定义*/ { ElemType data; struct Node * next; }Node, *LinkList; /* LinkList为结构指针类型*/ void init_linklist(LinkList *l)/*对单链表进行初始化*/ { *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=s; } else { flag=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 && k { pre=pre->next; k=k+1; }/*查找第i-1个结点*/ if(! (pre->next)) /* 即while循环是因为p->next=NULL或i<1而跳出的,而是因为没有找到合法的前驱位置 ,说明删除位置i不合法。 */ { printf("删除结点的位置i不合理! "); return ERROR; } r=pre->next; pre->next=pre->next->next; /*修改指针,删除结点r*/ *e = r->data; free(r); /*释放被删除的结点所占的内存空间*/ printf("成功删除结点! \n"); //printf("被删除的元素是: %c\n",*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("%c\n",p->data); p=p->next; } printf("请输入要删除的元素位置: \n"); scanf("%d",&x); e = (char*)malloc(sizeof(char)); DelList(l,x,e); p = l->next; while(p! =NULL) {printf("%c",p->data); p=p->next;} printf("\n"); } 执行结果: 3.栈 3.1链栈 程序: #include #include #defineTRUE1 #defineFALSE0 #defineStackElementTypeint typedefstructnode { StackElementTypedata; structnode*next; }LinkStackNode; typedefLinkStackNode*LinkStack; intPush(LinkStacktop,StackElementTypex) { LinkStackNode*temp; temp=(LinkStackNode*)malloc(sizeof(LinkStackNode)); if(temp==NULL) return(FALSE); temp->data=x; temp->next=top->next; top->next=temp; return(TRUE); } intPop(LinkStacktop,StackElementType*x) { LinkStackNode*temp; temp=top->next; if(temp==NULL) return(FALSE); top->next=temp->next; *x=temp->data; free(temp); return(TRUE); } intmain() { LinkStackNode*top; top=(LinkStackNode*)malloc(sizeof(LinkStackNode)); top->next=NULL; intflag=1; inta,x=0; printf("请输入链表的各元素值(输入0代表结束): \n"); while(flag) { scanf("%d",&a); if(a! =0) { Push(top,a); } else { flag=0; } } while(top->next! =NULL) { Pop(top,&x); printf("%d\t",x); } printf("\n"); return0; } 执行结果 3.2顺序栈 顺序栈进栈程序: #include #include #include #definestack_size50 typedefstruct { intelem[stack_size]; inttop; }seqstack; voidinitstack(seqstack*s) { s->top=-1; } intpush(seqstack*s,intx) { if(s->top==stack_size-1)return0; s->top++; s->elem[s->top]=x; return1; } voidOutStack(seqstack*p) { inti; if(p->top<0) printf("ThisisaEmptyStack! \n"); for(i=p->top;i>=0;i--) printf("%d",p->elem[i]); } intmain() { inta; inti,r; seqstack*s; s=(seqstack*)malloc(sizeof(seqstack)); initstack(s); printf("请输入长度: "); scanf("%d",&r); printf("请输入各元素值: \n"); for(i=0;i { s->top++; scanf("%d",&s->elem[i]); } printf("请输入要进栈的值: "); scanf("%d",&a); push(s,a); OutStack(s); return0; } 执行结果: 4.队列 顺序队列基本操作: #include #include #include #defineMaxSize20 typedefintElemType; typedefstruct { ElemTypedata[MaxSize]; intfront,rear;// }SqQueue;//顺序队列类型SqQueue的定义 //初始化队列 voidInitQueue(SqQueue*&q) { q=(SqQueue*)malloc(sizeof(SqQueue)); q->front=q->rear=0; } //销毁队列 voidClearQueue(SqQueue*&q) { free(q); } //判断顺序队列是否为空 voidQueueEmpty(SqQueue*q) { if(q->front==q->rear) printf("目前此顺序队列为空\n"); else printf("目前此顺序队列非空\n"); } //进队列 voidenQu
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 线性 表单 查找 插入 删除