当前位置：文档之家 › 单链表基本操作

单链表基本操作

  • 格式：doc
  • 大小：187.50 KB
  • 文档页数：11

一、系统功能图二、源代码/*本系统写于2013年10月27日广东工业大学西三743*注意实现了单链表的基本操作，包括建表，遍历，查询长度，插入，删除，排序*/#include<stdio.h>#include<malloc.h>#include<stdlib.h>//包含exit函数#include<conio.h>//包含清屏函数//定义结点typedef struct Node{int data;struct Node *next;}NODE,*PNODE;void show_list();//显示功能界面PNODE create_list();//创建void traverse_list(PNODE PHead);//遍历bool isempty_list(PNODE PHead);//判断空，功能函数，应该返回值int length_list(PNODE PHead);//链表长度，功能函数，应该返回一个整型void insert_list(PNODE PHead);//插入，应该有三个参数，头指针，插入位置，插入值，但为了让主函数简单，后两个放在函数体内void delete_list(PNODE PHead);//删除void sort_list(PNODE PHead);//排序//主函数int main(){PNODE PHead=NULL;char choice='0';show_list();printf("请建立链表，");PHead=create_list();//system("cls");//show_list();do{system("cls");show_list();printf("请选择你需要的操作");scanf("%c",&choice);switch(choice){case '1':printf("链表创建成功！");system("pause");break;case '2':traverse_list(PHead);break;case '3':sort_list(PHead);break;case'4':insert_list(PHead);break;case'5':delete_list(PHead);break;case '0':printf("感谢您的使用! \n");break;default:printf("输入非法，请重新输入\n");break;}}while(choice!='0');return 0;}//显示界面void show_list(){printf("***********************欢迎使用单链表演示系统***********************************");printf("********************************************************************************");printf("1.创建单链表\t 2.遍历链表\n");printf("3.排序链表\t 4.插入元素\n");printf("5.删除元素\t 0.退出\n");printf("********************************************************************* **********\n");}//创建链表PNODE create_list(){int n,i,a;PNODE head=(PNODE)malloc(sizeof(NODE));if(NULL==head){printf("内存分配失败，程序结束");exit(-1);}head->data=0;head->next=NULL;PNODE p,q;printf("输入结点数");scanf("%d",&n);if(n>0)//如果输入为0个结点则不用分配{for(i=0;i<n;i++){p=(PNODE )malloc(sizeof(NODE));if(NULL==p){printf("内存分配失败，程序结束");exit(-1);}printf("请输入第%d 个结点的值",i+1);scanf("%d",&a);p->data=a;if(NULL==head->next){head->next=p;//头结点也存放数据q=p;}else{q->next=p;q=p;}}q->next=NULL;}system("pause");return head;}//遍历链表void traverse_list(PNODE PHead) {PNODE p;p=PHead->next;if(false==isempty_list(PHead)){printf("链表为空\n");}while(p){printf("%d ",p->data);p=p->next;}printf("\n");system("pause");}//判断链表是否为空bool isempty_list(PNODE PHead) {if(!PHead->next){return false;}else{return true;}}//获取链表的长度int length_list(PNODE PHead){PNODE p;int len=0;p=PHead->next;//因为第一个结点不存数据while(p){len++;p=p->next;}return len;}//插入结点void insert_list(PNODE PHead){int i,val,post,len;PNODE pNew;//存放新结点PNODE p;//辅助结点，可以插入寻找位置p=PHead;printf("请输入插入位置");scanf("%d",&post);printf("请输入插入值");scanf("%d",&val);len=length_list(PHead);if(post<0||post>len+1)//因为不能插入末尾+1的位置{printf("输入位置有误");//如果有n 个结点，插入位置为m,则插入点在新链表中的位置为msystem("pause");return ;}else{pNew=(PNODE)malloc(sizeof(NODE));if(NULL==pNew){printf("内存分配失败，程序结束");exit(-1);}pNew->data=val;pNew->next=NULL;//如果插入最后一个位置时要把尾指针置空for(i=0;i<post-1;i++)//寻找插入位置{p=p->next;}pNew->next=p->next;//存放插入位置后一个结点指针p->next=pNew;}traverse_list(PHead);//测试插入效果}//删除结点void delete_list(PNODE PHead){int i,val,post,len;//val 存放删除的数据PNODE p,pFree;p=PHead;printf("请输入要删除的位置");scanf("%d",&post);len=length_list(PHead);if(post<0||post>len){printf("删除位置非法，删除失败");system("pause");return;}else{for(i=0;i<post-1;i++)//寻找删除位置{p=p->next;}}pFree=p->next;//要删除的结点，便于释放内存val=pFree->data;p->next=p->next->next;free(pFree);printf("删除成功，删除的是第%d 个结点，删除值为%d\n",post,val);system("pause");}//排序void sort_list(PNODE PHead){int i,j,len,t;//模仿数组的排序，本次使用冒泡法PNODE p,q;//p=PHead->next ;//因为第一个头结点不存放数据//q=p->next;//q为第二个结点len=length_list(PHead);for(i=0,p=PHead->next;i<len-1;i++,p=p->next)//n个结点只需要比较n-1次即可，注意结点也要向后移动{for(j=i+1,q=p->next;j<len;j++,q=q->next)//第一个分号语句不能写在前面，因为每轮比较后q的指针都已经移动了链表末尾{if(p->data >q->data){t=p->data;p->data=q->data;q->data=t;}}}printf("排序成功! \n");traverse_list(PHead);}三、运行与调试1.创建单链表2.遍历链表3.排序4.插入元素插入位置有误：5.删除元素6.退出。

合集下载

单链表的基本操作实验报告

单链表的基本操作实验报告

湖南第一师范学院信息科学与工程系实验报告课程名称：数据结构与算法成绩评定：实验项目名称：单链表的基本操作指导教师：学生姓名：沈丽桃学号： 10403080118 专业班级： 10教育技术实验项目类型：验证实验地点：科B305 实验时间： 2011 年 10 月20 日一、实验目的与要求：实验目的：实现线性链表的创建、查找、插入、删除与输出。

基本原理：单链表的基本操作二、实验环境：（硬件环境、软件环境）1.硬件环境：奔ⅣPC。

2.软件环境：Windows XP 操作系统，TC2.0或VC＋＋。

三、实验内容：（原理、操作步骤、程序代码等）#include<stdio.h>#include<stdlib.h>#include<malloc.h>struct celltype{int element;struct celltype*next;};typedef int position;void main(){struct celltype*head,*p;int x,choice;void INSERT(int x,struct celltype*p);void LOCATE(int x,struct celltype*p);void DELETE(int x,struct celltype*p);p=(struct celltype*)malloc(sizeof(struct celltype));head=p;p->element=0;p->next=NULL;printf(“Please option:1:Insert 2:Locate 3:Delete\n”);printf(“Please choose:”);scanf(“%d”,&choice);switch(choice)case 1:printf(“Please input a node:”);scanf(“%d”,&x);p=head;INSERT(x,p);for(p=head;p!=NULL;p=p->next)printf(“%d”,p->element);printf(“\n”);break;case 2:printf(“Please input the data you want to locate:”); scanf(“%d”,&x);p=head;LOCATE(x,p);break;case 3:printf(“Please input the data you want to delete:”); scanf(“%d”,&x);DELETE(x,p);for(p=head;p!=NULL;p=p->next)printf(“%d”,p->next);printf(“\n”);break;}void INSERT(int x,struct celltype*p){struct celltype*t,*q;q=(struct celltype*)malloc(sizeof(struct celltype)); q->next=x;while((x>p->element)&&(p!=NULL)){t=p;p=p->next;}if((x>p->element)&&(p->next!=NULL)){p->next=q;q->next=NULL;}else{q->next=p;t->next=q;}}void LOCATE(int x,struct celltype*p){while(p->next!=NULL)if(p->next->element==x)printf(“the number %d is in %d\n”,x,p);else printf(“the number not exist!\n”);}void DELETE(int x,struct celltype*p){while((p->element!=x)&&(p->next!=NULL)){t=p;p=p->next;}if(p->element==x)t->next=p->next}error C2018:unknown character ’Oxal’error C2065:’Please’:undeclared identifiererror C4024:’printf’:different types for formal and actual parameter 1error C4047:’function’:’const*differs in levers of indirection from ’int’error C2146:syntaxerror:missing’)’before identifier’option’error C2017:illegal escape sequenceerror C2059:syntax error:’)’error C2143:syntax error:missing’)’before’%’出现了很多错误，主要是因为printf里的一对双引号不是英文状态下的。

单链表的基本操作

单链表的基本操作

10）调用头插法的函数，分别输入10,20，分别回车：
11）调用尾插法的函数，分别输入30,40
12）查找单链表的第四个元素：
13）主函数中传入参数，删除单链表的第一个结点：
14）主函数传入参数，删除第0个未位置的元素，程序报错：
15）最后，输出单链表中的元素：
return 0;
}
6）编译，连接，运行源代码：
7）输入8，回车，并输入8个数，用空格分隔开，根据输出信息，可以看出，链表已经拆分为两个
五、实验总结
1.单链表采用的是数据+指针的表示形式，指针域总是指向下一个结
点（结构体）的地址，因此，在内存中的地址空间可以是不连续的，操作比顺序存储更加的方便
2.单链表使用时，需要用malloc函数申请地址空间，最后，删除元
素时，使用free函数释放空间。

数据结构实验报告--单链表

数据结构实验报告--单链表

数据结构实验报告--单链表数据结构实验报告--单链表1.引言1.1 研究目的本实验旨在通过实践的方式，深入了解单链表的数据结构以及相关操作，提升对数据结构的理解和应用能力。

1.2 实验内容本实验主要包括以下几个方面的内容：●单链表的基本定义和实现●单链表的插入、删除、遍历操作●单链表的逆置操作●单链表的查找和修改操作2.理论基础2.1 单链表的定义单链表是一种常见的线性数据结构，它由一系列的节点组成，每个节点包含数据和指向下一个节点的指针。

2.2 单链表的基本操作①单链表的插入操作在单链表中，可以通过插入操作在指定位置插入一个新节点，该操作主要包括以下步骤：●创建一个新的节点，并为其赋值●将新节点的next指针指向插入位置的后一个节点●将插入位置的前一个节点的next指针指向新节点②单链表的删除操作在单链表中，可以通过删除操作删除指定位置的节点，该操作主要包括以下步骤：●将删除位置的前一个节点的next指针指向删除位置的后一个节点●释放删除节点的内存③单链表的遍历操作单链表的遍历操作主要是依次访问链表中的每一个节点，并执行相应的操作。

④单链表的逆置操作单链表的逆置操作可以将一个单链表中的节点顺序进行颠倒。

⑤单链表的查找操作在单链表中，可以通过查找操作找到指定值的节点。

⑥单链表的修改操作在单链表中，可以通过修改操作修改指定位置的节点的值。

3.实验过程3.1 实验环境本次实验使用C语言进行编程，需要先安装相应的编程环境，如gcc编译器。

3.2 实验步骤①单链表的创建和初始化首先创建一个空链表，并初始化链表的头指针。

②单链表的插入操作按照需求，在链表的指定位置插入一个新节点。

③单链表的删除操作按照需求，删除链表中的指定位置的节点。

④单链表的遍历操作依次访问链表中的每一个节点，并输出其值。

⑤单链表的逆置操作将单链表中的节点顺序进行逆置。

⑥单链表的查找操作按照需求，在链表中查找指定值的节点。

3.2.7 单链表的修改操作按照需求，修改链表中指定位置的节点的值。

PTA7-4单链表基本操作

PTA7-4单链表基本操作

PTA7-4单链表基本操作7-4 单链表基本操作请编写程序实现单链表插⼊、删除结点等基本算法。

给定⼀个单链表和⼀系列插⼊、删除结点的操作序列，输出实施上述操作后的链表。

单链表数据域值为整数。

输⼊格式:输⼊第1⾏为1个正整数n，表⽰当前单链表长度；第2⾏为n个空格间隔的整数，为该链表n个元素的数据域值。

第3⾏为1个正整数m，表⽰对该链表施加的操作数量；接下来m⾏，每⾏表⽰⼀个操作，为2个或3个整数，格式为0 k d或1 k。

0 k d表⽰在链表第k个结点后插⼊⼀个数据域值为d的结点，若k=0则表⽰表头插⼊。

1 k表⽰删除链表中第k个结点，此时k不能为0。

注：操作序列中若含有不合法的操作（如在长度为5的链表中删除第8个结点、删除第0个结点等），则忽略该操作。

n和m不超过100000。

输出格式:输出为⼀⾏整数，表⽰实施上述m个操作后的链表，每个整数后⼀个空格。

输⼊数据保证结果链表不空。

输⼊样例:51 2 3 4 550 2 80 9 60 0 71 01 6输出样例:7 1 2 8 3 5参照课本的实现#include<iostream>#include<iomanip>#include<stdlib.h>using namespace std;typedef int ElemType;typedef int Status;#define ERROR 0#define OK 1#define OVERFLOW 3typedef struct LNode{ElemType data;struct LNode *next;}LNode ,*LinkList;Status ListInsert(LinkList L,int i,ElemType e){int j=0;LinkList p=L,s;while(p&&j<i-1) // 寻找第i-1个结点{p=p->next;j++;}if(!p||j>i-1) // i⼩于1或者⼤于表长return ERROR;s=(LinkList)malloc(sizeof(LNode)); // ⽣成新结点s->data=e; // 插⼊L中s->next=p->next;p->next=s;return OK;}Status ListDelete(LinkList L,int i){int j=0;LinkList p=L,q;while(p->next&&j<i-1) // 寻找第i个结点,并令p指向其前趋{p=p->next;j++;}if(!p->next||j>i-1) // 删除位置不合理return ERROR;q=p->next; // 删除并释放结点p->next=q->next;free(q);return OK;}int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);LinkList L;L=(LinkList)malloc(sizeof(LNode)); // 产⽣头结点,并使L指向此头结点 if(!L) // 存储分配失败exit(OVERFLOW);L->next=NULL;int n=0,m=0;LinkList db=L,da;cin>>n;for(int i=0;i<n;i++){da=(LinkList)malloc(sizeof(LNode));cin>>da->data;da->next=NULL;db->next=da;db = da;}cin>>m;for(int i=0;i<m;i++){int o,x,y;cin>>o;if(o==0){cin>>x>>y;ListInsert(L,x+1,y);}else if(o==1){cin>>x;ListDelete(L,x);}else{exit(ERROR);}}LinkList p=L->next;while(p!=NULL){cout<<p->data<<" ";p = p->next;}return 0;}。