班级：数学112班学号：201112010222姓名：吕文辉报告日期：2012/12/9
试验一：单链表
一、实验目的
（1）掌握单链表的存储结构形式及其描述。
（2）掌握单链表的建立、查找、插入和删除操作。
二、实验要求
（1）编写函数,实现随机产生或键盘输入一组元素,建立一个带头结点的单链表（无序）。（2）编写函数,实现遍历单链表。
（3）编写函数,实现把单向链表中元素逆置（不允许申请新的结点空间）。
（4）编写函数,建立一个非递减有序单链表。
（5）编写函数,利用以上算法，建立两个非递减有序单链表,然后合并成一个非递减链表。（6）编写函数,在非递减有序单链表中插入一个元素使链表仍然有序。
（7）编写函数,实现在非递减有序链表中删除值为x的结点。
（8）编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法。
三、实验代码：
#include
#include
#include
///////////////////////////////////////////
typedef char elemtype;
#define null 0
const int n=20;
int i=1;
typedef
struct node
{elemtype data;
struct node *p;
}node,*linklist;
///////////////////////////
void initlist(linklist L);//初始化单链表
void createfromhead(linklist L); //利用头插法建立单链表；
void textlinklist(linklist L); // 检测单链表；
void createfromtail(linklist L);//尾插法建立单链表；
void linklistnizhi(linklist k);//单链表的逆置；
void Lorder(elemtype a[n],int n);//给数组中元素排序；
void increaselinklist(linklist k); //给单链表中的元素排序；
linklist unittwolinklist(linklist k1,linklist k2); // 建立两个非递减有序单链表,然后合并成一个非递减链表。
void DeleteIncreaselinklist(linklist k); //编写函数,实现在非递减有序链表中删除值为x的结点void Insertelemtypelinklist(linklist k); //编写函数,在非递减有序单链表中插入一个元素使链表仍然有序
void alllinklistfunctionlwh(char s); //将所有函数的整合在一个函数里面；
void textlwhplinklist(linklist lwhp);
///////////////////////////////
int main()
{
cout<<"************************"< cout<<"头插法建立程序的眼演示实例"< cout<<"************************"< char s; cout<<"如果执行程序请输入L"< cin>>s; alllinklistfunctionlwh(s); //////////////////////////////////////////////// //调试程序时要用到的代码； /* node lwh; linklist lwhp; lwhp=&lwh; initlist(lwhp); cout<<"sizeof(node) "< cout<<"sizeof(lwhp)"< cout<<"第一个为表头指针，不放数据，由于用的头插法，故输出链表的顺序和输入的顺序恰好相反"< createfromhead(lwhp); createfromtail(lwhp); linklistnizhi(lwhp); 1逆置单链表； increaselinklist(lwhp); //给单链表中的元素排序； //建立另外一个单链表； node lwh1; linklist lwhp1; lwhp1=&lwh1; initlist(lwhp1); createfromtail(lwhp1); linklist lwhp2; lwhp2=unittwolinklist(lwhp,lwhp1); DeleteIncreaselinklist(lwhp); Insertelemtypelinklist(lwhp); char w; cout<<"如果想检验是否成功建立单链表，如果想检验就请输入y或Y"< cin>>w; if(w=='y'||w=='Y') { textlinklist(lwhp); } */ //调试程序时要用到的代码； ////////////////////////////////////////////////////// return 0; } ////////////////////////////////////////////////////////// void alllinklistfunctionlwh(char s) { int lwhf=1; if('L'==s) { cout<<"如果想运行初始化单链表函数请输入0 "< cout<<"如果想运行利用头插法建立单链表函数请输入1 "< cout<<"如果想运行尾插法建立单链表单链表请输入2 "< cout<<"如果想运行单链表的逆置函数请输入3 "< cout<<"如果想运行给数组中元素排序函数请输入4 "< cout<<"如果想运行建立两个非递减有序单链表,然后合并成一个非递减链表函数请输入5 "< cout<<"如果想运行实现在非递减有序链表中删除值为x的结点请输入6 "< cout<<"如果想运行在非递减有序单链表中插入一个元素使链表仍然有序表函数请输入7 "< cout<<"如果想运行退出该层函数请输入8 "< cout<<"请输入序号："< int i; char f; cin>>i; while(lwhf) { switch(i) { case 0: cout<<"初始化单链表函数"< node lwh0; linklist lwhp0; lwhp0=&lwh0; initlist(lwhp0); textlwhplinklist(lwhp0); cout<<"执行成功"< break; case 1: cout<<"利用头插法建立单链表函数"< cout<<"请输入字符"< node lwh1; linklist lwhp1; lwhp1=&lwh1; initlist(lwhp1); createfromhead(lwhp1); textlwhplinklist(lwhp1); break; case 2: cout<<" 尾插法建立单链表单链表"< cout<<"请输入字符"< node lwh2; linklist lwhp2; lwhp2=&lwh2; initlist(lwhp2); createfromtail(lwhp2); textlwhplinklist(lwhp2); break; case 3: cout<<"单链表的逆置函数"< cout<<"请输入字符"< node lwh3; linklist lwhp3; lwhp3=&lwh3; initlist(lwhp3); createfromtail(lwhp3); linklistnizhi(lwhp3); textlwhplinklist(lwhp3); break; case 4: cout<<"给数组中元素排序函数"< cout<<"请输入字符"< node lwh4; linklist lwhp4; lwhp4=&lwh4; initlist(lwhp4); createfromtail(lwhp4); increaselinklist(lwhp4); textlwhplinklist(lwhp4); break; case 5: cout<<"建立两个非递减有序单链表,然后合并成一个非递减链表函数"< cout<<"请输入第一个单链表的字符"< node lwh50; linklist lwhp50; lwhp50=&lwh50; initlist(lwhp50); createfromtail(lwhp50); cout<<"请输入第二个单链表的字符"< node lwh51; linklist lwhp51; lwhp51=&lwh51; initlist(lwhp51); createfromtail(lwhp51); linklist lwhp52; lwhp52=unittwolinklist(lwhp50,lwhp51); textlwhplinklist(lwhp52); break; case 6: cout<<"实现在非递减有序链表中删除值为x的结点"< cout<<"请输入字符"< node lwh6; linklist lwhp6; lwhp6=&lwh6; initlist(lwhp6); createfromtail(lwhp6); DeleteIncreaselinklist(lwhp6); textlwhplinklist(lwhp6); break; case 7: cout<<"在非递减有序单链表中插入一个元素使链表仍然有序表函数"< cout<<"请输入字符"< node lwh7; linklist lwhp7; lwhp7=&lwh7; initlist(lwhp7); createfromtail(lwhp7); Insertelemtypelinklist(lwhp7); textlwhplinklist(lwhp7); break; default: break; } cout<<"请重新选择序号"< cin>>i; if(i!=1&&i!=2&&i!=3&&i!=4&&i!=5&&i!=6&&i!=7&&i!=8) { cout<<"如果不想选择序号就输入字符"< cin>>f; if(f=='y'||f=='Y') { lwhf=1; } else lwhf=0; } } } } void textlwhplinklist(linklist lwhp) { char w; cout<<"如果想检验是否成功建立单链表，如果想检验就请输入y或Y"< cin>>w; if(w=='y'||w=='Y') { textlinklist(lwhp); } } /////////////////////////////////////////////////////////// // 所有函数的代码定义： void initlist(linklist L) { // L=(linklist)malloc(sizeof(node)); L->p=null; } //头插法建立单链表； void createfromhead(linklist L) { node *jiedian; // jiedian=L; char zimu; bool flag=true; // cin>>zimu; /* if(zimu!='&') { L->data=zimu; }*/ while(flag) { cin>>zimu; if(zimu!='&') { jiedian=(linklist)malloc(sizeof(node)); jiedian->data=zimu; jiedian->p=L->p; L->p=jiedian; // cout<<"jiedian->data"< } else flag=false; } } // 一个检测单链表是否建立成功的函数； void textlinklist(linklist L) { linklist p1; int i=1; p1=L->p; //建立指向单链表的第一个节点的指针； while(p1!=null) { cout<<"这是第"< p1=p1->p; i++; } } //利用尾插法建立单链表 void createfromtail(linklist L) { linklist s,r; bool flag=true; r=L; char c; while(flag) { cin>>c; if(c!='&') { s=(linklist)malloc(sizeof(node)); s->data=c; r->p=s; r=s; } else { r->p=null; flag=false; } } } //单链表中元素逆置； void linklistnizhi(linklist k)//假设k是个由尾插法建立起来的单链表；/*算法思想：只交换元素的位置，不改变节点的指针*/ { linklist k1,k2,k3; k1=k->p; k2=k1; k3=k1; int i=0,w; elemtype a[n]; while(k1!=null) { a[i]=k1->data; k1=k1->p; i++; } w=i; for(i=0;i { cout< } while(k3!=null) { k3->data=a[w-1]; k3=k3->p; w=w-1; } } //编写函数,建立一个非递减有序单链表 //编一个函数实现一个数组里的元素的逆置，该函数有2 //参数一个是指针，一个就是，数组的个数， void Lorder(elemtype a[n],int n) { int i,j,k; elemtype temp,*p; p=a; for(i=0;i { k=i; for(j=i+1;j if(*(p+j)<*(p+k)) k=j; temp=*(p+i); *(p+i)=*(p+k); *(p+k)=temp; } } //编写函数,建立一个非递减有序单链表 void increaselinklist(linklist k) { linklist k1,k2,k3; k1=k->p; k2=k1; k3=k1; int i=0,w; elemtype a[n]; while(k1!=null) { a[i]=k1->data; k1=k1->p; i++; } w=i; Lorder(a,w); for(i=0;i { cout< } int j=0; while(k3!=null&&j { k3->data=a[j]; k3=k3->p; j++; } } //编写函数,建立一个非递减有序单链表 //建立两个非递减有序单链表,然后合并成一个非递减链表。/*思路：想想办法把2个单链表中 的元素先排成有序的然后去出来在和并*/ linklist unittwolinklist(linklist k1,linklist k2) { increaselinklist(k2); increaselinklist(k1); linklist k3,p0,k4; k3=(linklist)malloc(sizeof(node)); k4=k3; /*由于让k3不停的向链表的末尾跑 所以设置一个k4把它的值保留下来，最后当函数的返回值*/ k2=k2->p; k1=k1->p; while(k1!=null&&k2!=null) { p0=(linklist)malloc(sizeof(node)); k3->p=p0; if(k1->data>k2->data) { p0->data=k2->data; k2=k2->p; } else{ p0->data=k1->data; k1=k1->p; } k3=p0; } while(k1!=null) { p0=(linklist)malloc(sizeof(node)); k3->p=p0; p0->data=k1->data; k1=k1->p; k3=p0; } while(k2!=null) { p0=(linklist)malloc(sizeof(node)); k3->p=p0; p0->data=k2->data; k2=k2->p; k3=p0; } k3->p=null; /* 当k3跑完时已经指向链表的最后一个单元 由于在把p0的值往单链表里连的时候用的k3->p=p0; 及每次在k3指向的那个单元赋值，当为最后一个单元的时候应该给其富null，这是为了单链表能通过textlinklist函数的检验 */ k3=k4; cout<<"~~~~~~~~~~~~~~~~~~~"< textlinklist(k4); cout<<"~~~~~~~~~~~~~~~~~~~~~~~~"< return k4; } //编写函数,在非递减有序单链表中插入一个元素使链表仍然有序 void Insertelemtypelinklist(linklist k) { increaselinklist(k); linklist k2,k3,k4; k4=k; int i=0; elemtype a1,a2; cout<<"请输入要插入的元素"< cin>>a2; k2=(linklist)malloc(sizeof(node)); k2->data=a2; while((k->p!=null)&&i==0) { a1=k->p->data; if(a2 { i=1; k3=k->p; k2->p=k3; k->p=k2; } k=k->p; } if(i==0) while(k->p==null) { k->p=k2; k2->p=null; } k=k4; } //编写函数,实现在非递减有序链表中删除值为x的结点 void DeleteIncreaselinklist(linklist k) { increaselinklist(k); linklist k2; /*引入i的作用是为了判断是否成功删除 如果成功删除后，就终止while循环 及目的已经达到，可以退出循环了 */ int i=0; elemtype a,b,c; bool flag=true; while(flag) { cout<<"输入你想删除的元素"< cin>>a; while((k->p!=null)&&(i==0)) { b=k->p->data; if(a==b) { k2=k->p->p; free(k->p); k->p=k2; i=1; cout<<"删除成功"< } else k=k->p; } if(i==0) cout<<"删除失败！"< cout<<"是否再次输入删除的元素如果想继续删除的话"; cout<<"就输入y或者Y"< cin>>c; if(c=='y'||c=='Y') flag=true; else flag=false; } } 单链表的创建、插入和删除 （数据结构） ——SVS #include Status DeleteList_Link(LinkList L,int i,ElemType e) //删除链表{ LinkList q,p=L;int j=0; while(p->next&&j 实验一单链表 #include "stdio.h" #include "stdlib.h" typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LNode,*LinkList; void creatLNode(LinkList &head) { int i,n; LNode *p; head=(LNode*)malloc(sizeof(LNode)); head->next=NULL; printf("请输入链表的元素个数："); scanf("%d",&n); for(i=n;i>0;i--) { p=(LNode*)malloc(sizeof(LNode)); printf("第%d个元素：",i); scanf("%d",&p->data); p->next=head->next; head->next=p; } } void InsertLNode(LinkList &L) { LNode *p=L; int i,j=0,e; printf("请输入你要插入的位置（超过链表长度的默认插在最后！）："); scanf("%d",&i); printf("请输入你要插入的元素："); scanf("%d",&e); while (p->next&&j LNode *s; s=(LNode*)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; } int DeleteLNode(LinkList &L,int i,int &e) { LNode *p; p=L; LNode *q; int j=0; while (p->next&&j 数组作为存放同类数据的集合，给我们在程序设计时带来很多的方便，增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定，不能在程序中进行调整，这样一来，在程序设计中针对不同问题有时需要3 0个大小的数组，有时需要5 0个数组的大小，难于统一。我们只能够根据可能的最大需求来定义数组，常常会造成一定存储空间的浪费。我们希望构造动态的数组，随时可以调整数组的大小，以满足不同问题的需要。链表就是我们需要的动态数组。它是在程序的执行过程中根据需要有数据存储就向系统要求申请存储空间，决不构成对存储区的浪费。 链表是一种复杂的数据结构，其数据之间的相互关系使链表分成三种：单链表、循环链表、双向链表，下面将逐一介绍。 7.4.1 单链表 图7 - 3是单链表的结构。 单链表有一个头节点h e a d，指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型，节点有两个成员：整型成员（实际需要保存的数据）和指向下一个结构体类型节点的指针即下一个节点的地址（事实上，此单链表是用于存放整型数据的动态数组）。链表按此结构对各节点的访问需从链表的头找起，后续节点的地址由当前节点给出。无论在表中访问那一个节点，都需要从链表的头开始，顺序向后查找。链表的尾节点由于无后续节点，其指针域为空，写作为N U L L。 图7 - 3还给出这样一层含义，链表中的各节点在内存的存储地址不是连续的，其各节点的地址是在需要时向系统申请分配的，系统根据内存的当前情况，既可以连续分配地址，也可以跳跃式分配地址。 看一下链表节点的数据结构定义： struct node { int num; struct node *p; } ; 在链表节点的定义中，除一个整型的成员外，成员p是指向与节点类型完全相同的指针。在链表节点的数据结构中，非常特殊的一点就是结构体内的指针域的数据类型使用了未定义成功的数据类型。这是在C中唯一规定可以先使用后定义的数据结构。 ?单链表的创建过程有以下几步： 1 ) 定义链表的数据结构。 2 ) 创建一个空表。 3 ) 利用m a l l o c ( )函数向系统申请分配一个节点。 4 ) 将新节点的指针成员赋值为空。若是空表，将新节点连接到表头；若是非空表，将新 节点接到表尾。 5 ) 判断一下是否有后续节点要接入链表，若有转到3 )，否则结束。 ?单链表的输出过程有以下几步 1) 找到表头。 数据结构的概念： 数据的逻辑结构+ 数据的存储结构+ 数据的操作； 数据的数值：=====》数据===》数值型数据整形浮点数ASCII 非数值型数据图片声音视频字符 =====》数据元素=====》基本项组成（字段，域，属性）的记录。 数据的结构： 逻辑结构 ----》线性结构（线性表，栈，队列） ----》顺序结构 ----》链式结构 ----》非线性结构(树，二叉树，图) ----》顺序结构 ----》链式结构 存储结构 -----》顺序存储 -----》链式存储 -----》索引存储 -----》哈希存储==散列存储 数据的操作： 增 删 改 查 DS ====》数据结构===》DS = (D,R); 数据结构中算法： 1、定义：有穷规则的有序集合。 2、特性： 有穷性 确定性 输入 输出 3、算法效率的衡量 时间复杂度计算===》算法中可执行依据的频度之和，记为：T(n)。 是时间的一种估计值不是准确值。 计算结果的分析：1 将最终结果的多项式中常数项去掉 2 只保留所有多项式中最高阶的项 3 最后的最高阶项要去掉其常数项 时间复杂度的量级关系： 常量阶====》对数阶===》线性阶===》线性对数阶====》平方阶===》立方阶===》指数阶 以上关系可以根据曲线图来判断算法对时间复杂度的要求 空间复杂度计算====》算法执行过程中所占用的存储空间的量级，记为：D（n）。 计算方法是在运行过程中申请的动态内存的量级计算。 ///////////////////////////////////////////////////////////////////////////////////////////////// 线性表 顺序存储====》顺序表（数组） 链式存储====》单链表 特征：对于非空表，a0是表头没有前驱。 an-1 是表尾没有后继 ai的每个元素都有一个直接前驱和直接后继 基本操作：创建表=====》增加元素====》删除元素====》改变元素值====》查询元素 1、顺序表的操作 1.1 创建顺序表=====》定义个指定类型的数组====》int a[100] ={0}; 单链表的初始化，建立，插入，查找，删除。 #include <stdio.h> #include <stdlib.h> typedef int ElemType; //定义结点类型 typedef struct Node { ElemType data; //单链表中的数据域 struct Node *next; //单链表的指针域 }Node,*LinkedList; //单链表的初始化 LinkedList LinkedListInit() { Node *L; L = (Node *)malloc(sizeof(Node)); //申请结点空间 if(L == NULL) //判断是否有足够的内存空间 printf("申请内存空间失败\n"); L->next = NULL; //将next设置为NULL,初始长度为0的单链表return L; } //单链表的建立1，头插法建立单链表 LinkedList LinkedListCreatH() { Node *L; L = (Node *)malloc(sizeof(Node)); //申请头结点空间 L->next = NULL; //初始化一个空链表 ElemType x; //x为链表数据域中的数据 while(scanf("%d",&x) != EOF) { Node *p; p = (Node *)malloc(sizeof(Node)); //申请新的结点 p->data = x; //结点数据域赋值 《数据结构》实验报告 1、实验名称:设计循环单链表 2、实验日期: 2013-3-26 3、基本要求： 1）循环单链表的操作，包括初始化、求数据元素个数、插入、删除、取数据元素； 2）设计一个测试主函数实际运行验证所设计循环单链表的正确性。 4、测试数据： 依次输入1，2，3，4，5，6，7，8，9，10，删除5，再依次输出数据元素。 5、算法思想或算法步骤: 主函数主要是在带头结点的循环单链表中删除第i个结点，其主要思想是在循环单链表中寻找到第i-1个结点并由指针p指示，然后让指针s指向a[i]结点，并把数据元素a[i]的值赋给x，最后把a[i]结点脱链，并动态释放a[i]结点的存储空间。 6、模块划分： 1）头文件LinList.h。头文件LinList.h中包括：结点结构体定义、初始化操作、求当前数据个数、插入一个结点操作、删除一个结点操作以及取一个数据元素操作； 2）实现文件dlb.cpp。包含主函数void main(void)，其功能是测试所设计的循环单链表的正确性。 7、数据结构： 链表中的结点的结构体定义如下： typedef struct Node { DataType data; struct Node *next; }SLNode; 8、源程序： 源程序存放在两个文件中，即头文件LinList.h和实现文件dlb.cpp。//头文件LinList.h typedef struct Node { DataType data; struct Node *next; }SLNode; void ListInitiate(SLNode **head) //初始化 { *head=(SLNode *)malloc(sizeof(SLNode)); //申请头结点，由head指示其地址 (*head)->next=*head; } #include 《数据结构课程设计》报告 题目：单链表操作 专业：计算机科学与技术 班级： 单链表操作 针对带头结点的单循环链表，编写实现以下操作的算法函数。 实现要求： ⑴单链表建立函数create：先输入数据到一维数组A[M]中，然后根据一维 数组A[M]建立一个单循环链表，使链表中个元素的次序与A[M]中各元素的次序相同，要求该函数的时间复杂度为O(m)； ⑵定位查找函数Locate：在所建立的单循环链表中查找并返回值为key的 第1个元素的结点指针；若找不到，则返回NULL； ⑶求出该链表中值最大和次大的元素值，要求该算法的时间复杂度为O(m)， 最大和次大的元素值通过指针变量带回，函数不需要返回值； ⑷将链表中所有值比key(值key通过形参传入)小的结点作为值为key的结 点前驱，所有值比key大的结点作为值为key的结点后继，并尽量保持原有结点之间的顺序，要求该算法的时间复杂度为O(m); ⑸设计一个菜单，具有上述处理要求和退出系统功能。 ⒈本人完成的工作： 一、定义结构体：LNode 二、编写以下函数： （1）建立单循环链表 （2）建立定位查找函数 （3）求出链表中最大和次大值 （4）将链表中的值和输入的Key比较，小的作为key前驱结点，大的作为key 的后继结点 三、设计具有上述处理要求和退出系统菜单 ⒉所采用的数据结构：单链表 数据结构的定义： typedef struct Node //定义结点的结构体 { DataType data; //数据域 struct Node *next; //指针域 }LNode; //结点的类型 ⒊所设计的函数 （1）Create(void) LNode *Create(void) //建立单循环链表，链表头结点head作为返回值{ int i,j,n,A[M]; //建立数组A【M】 LNode *head,*p,*move; head=(LNode*)malloc(sizeof(LNode)); //创建空单循环链表head->next=head; move=head; printf("请输入数组元素的个数："); //输入数组 scanf("%d",&n); printf("请输入数组："); for(i=0;i #include return l; } voidPrintlist(linklist l) { linklist p; p=l->next; while(p) { printf("%d\t",p->data); p=p->next; } printf("\n"); } 目录 1 选题背景 (2) 2 方案与论证 (3) 2.1 链表的概念和作用 (3) 2.3 算法的设计思想 (4) 2.4 相关图例 (5) 2.4.1 单链表的结点结构 (5) 2.4.2 算法流程图 (5) 3 实验结果 (6) 3.1 链表的建立 (6) 3.2 单链表的插入 (6) 3.3 单链表的输出 (7) 3.4 查找元素 (7) 3.5 单链表的删除 (8) 3.6 显示链表中的元素个数（计数） (9) 4 结果分析 (10) 4.1 单链表的结构 (10) 4.2 单链表的操作特点 (10) 4.2.1 顺链操作技术 (10) 4.2.2 指针保留技术 (10) 4.3 链表处理中的相关技术 (10) 5 设计体会及今后的改进意见 (11) 参考文献 (12) 附录代码： (13) 1 选题背景 陈火旺院士把计算机60多年的发展成就概括为五个“一”：开辟一个新时代----信息时代，形成一个新产业----信息产业，产生一个新科学----计算机科学与技术，开创一种新的科研方法----计算方法，开辟一种新文化----计算机文化，这一概括深刻影响了计算机对社会发展所产生的广泛而深远的影响。 数据结构和算法是计算机求解问题过程的两大基石。著名的计算机科学家P.Wegner指出，“在工业革命中其核心作用的是能量，而在计算机革命中其核心作用的是信息”。计算机科学就是“一种关于信息结构转换的科学”。信息结构（数据结构）是计算机科学研究的基本课题，数据结构又是算法研究的基础。 2 方案与论证 2.1 链表的概念和作用 链表是一种链式存储结构，链表属于线性表，采用链式存储结构，也是常用的动态存储方法。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。 以“结点的序列”表示线性表称作线性链表（单链表） 单链表是链式存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。 因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i 单链表 1、链接存储方法 链接方式存储的线性表简称为链表（Linked List）。 链表的具体存储表示为： ① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的） ② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)） 注意： 链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。 2、链表的结点结构 ┌───┬───┐ │data │next │ └───┴───┘ data域--存放结点值的数据域 next域--存放结点的直接后继的地址（位置）的指针域（链域） 注意： ①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。 ②每个结点只有一个链域的链表称为单链表（Single Linked List）。 typedef struct LNode//结点类型 { int data;//数值域 struct LNode *next;//指针域 }CrLNode,*CrLinklist; #include"Base.h" #include"construct.h" #include"circulate_operation.c" int main() { CrLinklist L; int i,choice,n,e; printf("请输入链表元素个数:"); scanf("%d",&n); L=Initlist_L(n); printf("请选择执行语句，选择输入1，执行插入操作或选择输入2，执行删除操作:"); scanf("%d",&choice); switch(choice) { case 1: { printf("请输入插入元素的位置:"); scanf("%d",&i); if(i<=0||i>n) printf("您输入的值不合法"); else printf("请输入插入元素的值："); scanf("%d",&e); L=ListInsert_L(L,i,e); printf("插入后的链表为："); printlist_L(L); };break; case 2: { printf("请输入删除元素的位置:"); scanf("%d",&i); if(i<=0||i>n) printf("您输入的值不合法"); else L=ListDelete_L(L,i); printf("删除后的链表为"); printlist_L(L); };break; } } CrLinklist Initlist_L(int n)//创建带头结点的单链表 { CrLinklist L; CrLinklist P; int i; L=(CrLinklist)malloc(sizeof(CrLNode)); L->next=L;/* 先建立一个带头结点的单链表*/ printf("请输入%d个数据\n",n); for(i=n;i>0;--i) { P=(CrLinklist)malloc(sizeof(CrLNode)); /* 生成新结点*/ scanf("%d",&P->data); /* 输入元素值*/ P->next=L->next; /* 插入到表头*/ L->next=P; } return L; } CrLinklist ListInsert_L(CrLinklist L,int i,int e)//单链表的插入 { CrLinklist P,S; int j; P=L; j=0; while(P&&j #include"stdio.h" #include"stdlib.h" typedef struct node { int data; struct node *next; }Lnode,*Linklist; input(Lnode *p,int n)//实现用键盘顺序输入链表数据{ Lnode *s;int i,d; printf("请输入数据："); for(i=1;i<=n;i++) { if(i==1) { scanf("%d",&d); p->data=d; continue; } if(n==1)break; scanf("%d",&d); s=(Linklist)malloc(sizeof(Lnode)); s->data=d; p->next=s; s->next=NULL; p=s;//使当前指针指向链表尾部节点 } } output(Lnode *p,int n)//实现输出当前链表所有数据 { int i=1; printf("当前链表的值为："); while(p->next!=NULL) { printf("%d ",p->data); p=p->next; i++; } if(i==n)//当是最后一个节点时，其next已经是空，所以最后一个节点数据无法用while循环写出，所以另用了一个计数器i printf("%d",p->data); } insert(Lnode *p,int i,int e)//实现在第i个元素之后插入新元素{ int j=0;Lnode *s; while(p&&j #include } template #include "stdio.h"/*单链表方式的实现*/ #include "malloc.h" typedef char ElemType ; typedef struct LNode/*定义链表结点类型*/ { ElemType data ; struct LNode *next; }LNode,*LinkList;/*注意与前面定义方式的异同*/ /*建立链表，输入元素，头插法建立带头结点的单链表(逆序)，输入0结束*/ LinkList CreateList_L(LinkList head) { ElemType temp; LinkList p; printf("请输入结点值(输入0结束)"); fflush(stdin); scanf("%c",&temp); while(temp!='0') { if(('A'<=temp&&temp<='Z')||('a'<=temp&&temp<='z')) { p=(LinkList)malloc(sizeof(LNode));/*生成新的结点*/ p->data=temp; p->next=head->next; head->next=p;/*在链表头部插入结点，即头插法*/ } printf("请输入结点值(输入0结束)："); fflush(stdin); scanf("%c",&temp); } return head; } /*顺序输出链表的内容*/ void ListPint_L(LinkList head) { LinkList p; int i=0; p=head->next; while(p!=NULL) { i++; printf("单链表第%d个元素是：",i); 单链表实验报告 一、实验目的 1、帮助读者复习C++语言程序设计中的知识。 2、熟悉线性表的逻辑结构。 3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。 二、实验内容 [问题描述] 实现带头结点的单链表的建立、求长度，取元素、修改元素、插入、删除等单链表的基本操作。 [基本要求] （1）依次从键盘读入数据，建立带头结点的单链表； （2）输出单链表中的数据元素 （3）求单链表的长度； （4）根据指定条件能够取元素和修改元素； （5）实现在指定位置插入和删除元素的功能。 三、算法设计 （1）建立带表头结点的单链表；首先输入结束标志，然后建立循环逐个输入数据，直到输入结束标志。 （2）输出单链表中所有结点的数据域值；首先获得表头结点地址，然后建立循环逐个输出数据，直到地址为空。 （3）输入x,y在第一个数据域值为x的结点之后插入结点y，若无结点x，则在表尾插入结点y;建立两个结构体指针，一个指向当前结点，另一个指向当前结点的上一结点，建立循环扫描链表。当当前结点指针域不为空且数据域等于x的时候，申请结点并给此结点数据域赋值为y，然后插入当前结点后面，退出函数；当当前结点指针域为空的时候，申请结点并给此结点数据域赋值为y，插入当前结点后面，退出函数。 （4）输入k，删除单链表中所有的结点k，并输出被删除结点的个数。建立三个结构体指针，一个指向当前结点，另一个指向当前结点的上一结点，最后一个备用；建立整形变量l=0；建立循环扫描链表。当当前结点指针域为空的时候，如果当前结点数据域等于k，删除此结点，l++，跳出循环，结束操作；如果当前结点数据域不等于k，跳出循环，结束操作。当当前结点指针域不为空的时候，如果当前结点数据域等于k，删除此结点，l++，继续循环操作；如果当前结点数据域不等于k，指针向后继续扫描。循环结束后函数返回变量l的值，l便是删除的结点的个数。 单链表的插入和删除实验日志 指导教师刘锐实验时间2010 年10 月11 日 学院数理专业数学与应用数学 班级学号姓名实验室S331-A 实验题目：单链表的插入和删除 实验目的：了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 实验要求：建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。 实验主要步骤： 1、分析、理解程序(相关程序见附录) 。 2、调试程序，并设计输入字符串数据（如：aa, bb , cc , dd, ee，#），测试程序的如下功能： 不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。 3、修改程序： （1）增加插入结点的功能。 （2）将建立链表的方法改为头插入法。 实验结果： 1、不允许重复字符串的插入功能结果如下： 3、删除和插入结点的功能如下： 心得体会： 通过这次实验我学会了单链表的建立和删除，基本了解了线性表的逻辑结构和链式存储结构，掌握了单链表的基本算法，使我受益匪浅。在调试程序的过程中，遇见了一系列的问题，后来在同学的帮助下，修改了几个语句后，终于把它给调试出来了。有时候一个标点符号的问题就可能导致程序无法运行。所以在分析调试程序的时候一定要仔细。 附加程序代码： 1、调试之后的程序如下（其中蓝色字体部分为修改过的）： #include"stdio.h" #include"string.h" #include"stdlib.h" #include"ctype.h" typedef struct node //定义结点 { char data[10]; //结点的数据域为字符串 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自定义LinkList单链表类型 LinkList CreatListR1(); //函数，用尾插入法建立带头结点的单链表ListNode *LocateNode(); //函数，按值查找结点 第2章自测卷答案 一、填空 1.顺序表中逻辑上相邻的元素的物理位置相互相邻。单链表中逻辑上相邻的元素的物理位置不 相邻。 2.在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点值域指示。 3．在n个结点的单链表中要删除已知结点*p，需找到它的地址。 二、判断正误（在正确的说法后面打勾，反之打叉） 1. 链表的每个结点中都恰好包含一个指针。X 2. 链表的物理存储结构具有同链表一样的顺序。X 3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。X 4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。Y 5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。Y 6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。X 7. 线性表在物理存储空间中也一定是连续的。X 8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。X 9. 顺序存储方式只能用于存储线性结构。X 10. 线性表的逻辑顺序与存储顺序总是一致的。X 三、单项选择题 （A）1. 链接存储的存储结构所占存储空间： （A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 （B）只有一部分，存放结点值 （C）只有一部分，存储表示结点间关系的指针 （D）分两部分，一部分存放结点值，另一部分存放结点所占单元数 （B）2. 链表是一种采用存储结构存储的线性表； （A）顺序（B）链式（C）星式（D）网状 （D）3. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址: （A）必须是连续的（B）部分地址必须是连续的 （C）一定是不连续的（D）连续或不连续都可以 （B）4．线性表Ｌ在情况下适用于使用链式结构实现。 （Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入 （Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂 （C）5．单链表的存储密度 （Ａ）大于1；（Ｂ）等于1；（Ｃ）小于1；（Ｄ）不能确定 （A）6、在单链表的一个结点中有个指针。 . 实验一、单链表的插入和删除 一、目的 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 二、要求： 建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。 三、程序源代码 #include"stdio.h" #include"string.h" #include"stdlib.h" #include"ctype.h" typedef struct node //定义结点 { char data[10]; //结点的数据域为字符串 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自定义LinkList单链表类型 LinkList CreatListR1(); //函数，用尾插入法建立带头结点的单链表 ListNode *LocateNode(); //函数，按值查找结点 void DeleteList(); //函数，删除指定值的结点void printlist(); //函数，打印链表中的所有值 void DeleteAll(); //函数，删除所有结点，释放内存 //==========主函数============== void main() { char ch[10],num[10]; LinkList head; head=CreatListR1(); //用尾插入法建立单链表，返回头指针printlist(head); //遍历链表输出其值 printf(" Delete node (y/n):");//输入“y”或“n”去选择是否删除结点scanf("%s",num); if(strcmp(num,"y")==0 || strcmp(num,"Y")==0){ printf("Please input Delete_data:"); scanf("%s",ch); //输入要删除的字符串 DeleteList(head,ch); printlist(head); } DeleteAll(head); //删除所有结点，释放内存 } //==========用尾插入法建立带头结点的单链表 单链表的基本操作 #include r->next=p->next; p->next=r; } void puter(linklist linker) { linklist p; p=linker->next; while(p!=NULL) { printf("%c ",p->ch); p=p->next; } } void delet(linklist head ,int i) { int j=0; linklist r,p; p=head->next; while(p&&j单链表的创建、插入和删除
数据结构 单链表基本操作代码
C语言链表的建立、插入和删除
数据结构 单链表详解
单链表的初始化,建立,插入,查找,删除
《数据结构》实验报告 设计循环单链表
链表建立
数据结构课程设计单链表操作
头插法建立单链表
数据结构课程设计单链表
数据结构循环链表插入和删除源代码代码
c数据结构单链表的建立与基本应用
数据结构单链表输入输出(c++)
单链表的建立及其基本操作的实现(完整程序)
数据结构-单链表实验报告
数据结构--单链表的插入和删除
第三章 单链表 题目和答案
单链表的插入和删除实验报告
单链表的建立及插入删除操作-c语言
相关主题
文本预览