实验二线性表的建立插入删除

实验二 线性表

2.1实验目的：

（1）掌握线性表的顺序存储结构的定义及C 语言实现。

（2）掌握线性表在顺序存储结构即顺序表中的各种基本操作。

（3）掌握线性表的链式存储结构——单链表的定义及C 语言实现。

（4）掌握线性表在链式存储结构——单链表中的各种基本操作。

2.2实验要求：

（1） 复习课本中有关线性表的知识；

（2） 用C 语言完成算法和程序设计并上机调试通过；

（3） 撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括

时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果）。

2.3基础实验

[实验1] 顺序表的建立

实验内容与要求:

建立一个含n 个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。

分析:

顺序表是线性表的顺序存储结构，是指用一组连续的内存单元依次存放线性表的数据元素。在顺序存储结构下，逻辑关系相邻的两个元素在物理位置上也相邻，这是顺序表的特点。 若一个数据元素仅占一个存储单元，则其存储方式参图2-1。

从图中可见，第i 个数据元素的地址为：

Loc(a i )=loc(a 1)+(i-1)

假设线性表中每个数据元素占用 l 个存储单元，那么在顺序表中，线性表的第i 个元素的存储位置与第1个元素的存储位置的关系是：

Loc(a i ) = Loc( a 1)+ (i – 1) l

存储位置 元素序号 a 1 a 2 … a i … a n 1 2 i n L L+1 L+(i-1) L+(n-1) 图2-1顺序表存储示意图

这里 Loc(a i)是第 i 个元素的存储位置, Loc( a1 ) 是第1个元素的存储位置，也称为线性表的基址；显然，顺序表便于进行随机访问，故线性表的顺序存储结构即顺序表是一种随机存储的结构。

由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。因此利用C语言的结构体类型定义顺序表：#define LIST_INIT_SIZE 100

#define LISTINCREMENT 10

typedef int ElemType; // 线性表中存放整型元素(将抽象数据类型ElemType typedef struct // 具体化int类型

{

ElemType *elem; //存储空间首地址

int length; //线性表的当前长度

int listsize; //当前分配的存储单元数，（以sizeof(ElemType)为单位）}SqList;

将此结构定义放在一个头文件SqList.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的初始化及常量的定义。

参考程序:

// 头文件 SqList.h的内容如下：

#include

#include

#define LIST_INIT_SIZE 100

#define LISTINCREMENT 10

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

#define OVERFLOW -2

typedef int ElemType;

typedef int Status;

typedef struct{

ElemType *elem;

int length;

int listsize;

}SqList;

Status InitList_Sq(SqList *L)

{

L->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));

if(!L->elem) return (OVERFLOW);

L->length=0;

L->listsize=LIST_INIT_SIZE;

return OK;

}

Status CreatList_Sq(SqList *L,int n)

{

int i;

printf("输入%d个整数:\n",n);

for(i=0;i

scanf("\n%d",&L->elem[i]);

return OK;

}

// 以下是整个源程序(保存在shiyan2_1_1.c文件中)：

#include

#include "SqList.h"

void main()

{

int i,n;

SqList a;

SqList *l=&a;

if(InitList_Sq(l)=-2) printf("分配失败\n") ;

printf("\n 输入要建立的线性表l的长度n:");//输入线性表的长度

scanf("%d",&n);

l->length=n;

printf("线性表的长度是: %d\n",l->length);

CreatList_Sq(l,n);//生成线性表

printf("输出线性表l中的元素值: ");//输出线性表中的元素

for(i=0;ilength;i++)

printf("%7d",l->elem[i]);

getch();

}

[实验2] 顺序表的插入

实验内容与要求：

利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68，通过对比插入元素前后的线性表发生的变化，判断插入操作是否正确。

分析：

从插入位置到最后位置的所有元素都要后移一位，使空出的位置插入元素值e。一般在第i个元素之前（1<=i<=n）插入一个新元素时，需要有n-i+1个元素进行移动。但是，插入的位置是不固定的，当插入位置i=１时，全部元素都得移动，需n次移动，当i=2时，移动n-1个元素，依次类似，当i=n时，仅需移动元素一次。如图2-2所示。

注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。

参考程序：

//保存在shiyan2_1_2.c 文件中

#include

#include

#include "SqList.h"

Status ListInsert_Sq(SqList *L,int i,ElemType e){

//在线性表L 中的第i 个位置前插入一个值为e 的元素

// i 的取值范围：1<=i<=ListLength_Sq(L)

ElemType *newbase,*q,*p;

if(i<1||i>L->length+1) return ERROR; //i 值不合法

if(L->length>=L->listsize){ //当前存储空间已满，增加分配量 newbase=(ElemType*)realloc(L->elem,

(L->listsize+LISTINCREMENT)*sizeof(ElemType));

if(!newbase) return (OVERFLOW); //存储分配失败

L->elem=newbase; //新基址

L->length=+LISTINCREMENT; //增加存储容量

}//if

q=&(L->elem[i-1]); //q 为插入位置

for(p=&(L->elem[L->length-1]);p>=q;--p) *(p+1)=*p;

//插入位置及以后的元素右移 *q=e; //插入e

++L->length; //表长增1

return OK;

}//ListInsert_Sq

void main()

{

int n,i,x;

SqList *L,a;

L=&a;

InitList_Sq(L);

printf("\n 输入要建立的线性表L 的长度:"); scanf("%d",&n);

下标 数值 a 1 a 2 … a i-1 a i a i+1 … a n … … 0 1 … i-2 i-1 i … n-1 … listsize-1 a 1 a 2 … a i-1

e a i a i+1 … a n … 下标 数值

0 1 … i-2 i-1 i … n-1 …

listsize-1 图2-2顺序表中插入元素e 前后状态 插入前 插入后

L->length=n;

CreatList_Sq(L,n);

printf("\n 插入元素之前线性表L的长度是: %d ",L->length);

printf("\n 插入元素之前线性表L中的元素是:");

for(i=0;ilength;i++)

printf("%5d", L->elem[i]);

printf("\n 输入要插入元素的位置:");

scanf("%d",&i);

printf("\n 输入要插入的元素的值:");

scanf("\n %d",&x);

if(ListInsert_Sq(L,i,x)>0)

{

printf("\n 插入元素之后线性表L的长度是: %d ",L->length);

printf("\n 插入元素之后线性表L的元素是:\n");

for(i=0;ilength;i++)

printf("%5d", L->elem[i]);

}//if

else

printf("can't insert the data!\n");

getch();

}

顺序表的创建插入与删除

#include #define maxsize 1024 //定义maxsize是1024 #define inplen 10 //定义inplen是10 typedefint datatype; typedefstruct { datatype data[maxsize]; int last; }sequenlist; //创建一个顺序表并且将之初始化 sequenlist *CreatInit(void) { sequenlist *l; l = new sequenlist( ); //使用动态分配sequenlist空间大小l->last=-1; //空表 return l; } //打印出顺序表 void println(sequenlist *head) { sequenlist *p = head; inti = 0; printf(" Now the squenlist is:"); for (i = 0; i<= p->last; i++) { printf("%d ", p->data[i]); } } //计算出顺序表的长度 int Length(sequenlist *head) { return head->last+1; } //给顺序表结点data[i]赋值 sequenlist *Setvalue(sequenlist *head) { inti; sequenlist *p = head; for (i = 0; idata[i]); //键盘上输入10 个结点的值} p->last = i-1;

顺序表的查找、插入与删除实验报告

《数据结构》实验报告一 学院：班级： 学号：姓名： 日期：程序名 一、上机实验的问题和要求： 顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求： 1.从键盘输入10个整数，产生顺序表，并输入结点值。 2.从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找 不到，则显示“找不到”。 3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插 入在对应位置上，输出顺序表所有结点值，观察输出结果。 4.从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。 二、源程序及注释： #include #include /*顺序表的定义：*/ #include #define ListSize 100 /*表空间大小可根据实际需要而定，这里假设为100*/ typedef int DataType; /*DataType可以是任何相应的数据类型如int, float或char*/ typedef struct { DataType data[ListSize]; /*向量data用于存放表结点*/ int length; /*当前的表长度*/ }SeqList; void main() { SeqList L; int i,x; int n=10; /*欲建立的顺序表长度*/ L.length=0; void CreateList(SeqList *L,int n); void PrintList(SeqList L,int n); int LocateList(SeqList L,DataType x); void InsertList(SeqList *L,DataType x,int i); void DeleteList(SeqList *L,int i);

01顺序结构的线性表插入删除查找

//* * * * * * * * * * * * * * * * * * * * * * * //PROGRAM NAME :顺序结构的线性表 * //CONTENT :插入,删除,查找 * //* * * * * * * * * * * * * * * * * * * * * * * #include #include #include #define MAX 30 //定义线性表的最大长度 enum BOOL{False,True}; //定义BOOL型 typedef struct{ char elem[MAX]; //线性表 int last; //last指示当前线性表的长度 }sqlisttp; void initial(sqlisttp &); //初始化线性表 BOOL insert(sqlisttp &,int,char); //在线性表中插入元素 BOOL del(sqlisttp&,int,char &); //在线性表中删除元素 int locate(sqlisttp,char); //在线性表中定位元素 void print(sqlisttp); //显示线性表中所有元素 void main() {sqlisttp S; //S为一线性表 int loc,flag=1; char j,ch; BOOL temp; textbackground(3); //设置屏幕颜色 textcolor(15); clrscr(); //---------------------------程序解说-------------------------- printf("本程序用来实现顺序结构的线性表。\n"); printf("可以实现查找、插入、删除等操作。\n"); //------------------------------------------------------------- initial(S); //初始化线性表 while(flag) { printf("请选择:\n"); printf("1.显示所有元素\n"); printf("2.插入一个元素\n"); printf("3.删除一个元素\n"); printf("4.查找一个元素\n"); printf("5.退出程序 \n"); scanf(" %c",&j); switch(j) {case '1':print(S); break; //显示所有元素 case '2':{printf("请输入要插入的元素(一个字符)和插入位置:\n"); printf("格式：字符，位置；例如:a,2\n"); scanf(" %c,%d",&ch,&loc); //输入要插入的元素和插入的位置

单链表的创建、插入和删除

单链表的创建、插入和删除 （数据结构） ——SVS #include #include #include typedef int ElemType; typedef int Status; typedef struct LNode { ElemType data; struct LNode *next; }LNode,*LinkList; void InitList_Link(LinkList L) //创建空链表 { L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; } Status InsertList_Link(LinkList L,int i,ElemType e) //插入链表 { LinkList s,p=L; int j=0; while(p&&jnext;j++;} if(!p||j>i-1)return -1; s=(LinkList)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; return 1; }

Status DeleteList_Link(LinkList L,int i,ElemType e) //删除链表{ LinkList q,p=L;int j=0; while(p->next&&jnext;j++;} if(!(p->next)||j>i-1)return -1; q=p->next; e=q->data; p->next=q->next; free(q); return 1; } void OutPutList_Link(LinkList L) //输出链表 { printf("表中值为："); LinkList p=L->next; while(p) { printf("%d ",p->data); p=p->next; } printf("\n"); } void CreateList_Link(LinkList L,int len) //创建链表 { int i; LinkList s,p=L; for(i=0;idata); s->next=NULL; p->next=s; p=s; } } int main() { int len; LinkList L; ElemType e; L=(LinkList)malloc(sizeof(LNode));

数据结构-顺序表的查找插入与删除

一、上机实验的问题和要求： 顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求： 1.从键盘输入10个整数，产生顺序表，并输入结点值。 2.从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找 不到，则显示“找不到”。 3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插 入在对应位置上，输出顺序表所有结点值，观察输出结果。 4.从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。 二、源程序及注释： #include #include /*顺序表的定义：*/ #include #define ListSize 100 /*表空间大小可根据实际需要而定，这里假设为100*/ typedef int DataType; /*DataType可以是任何相应的数据类型如int, float或char*/ typedef struct { DataType data[ListSize]; /*向量data用于存放表结点*/ int length; /*当前的表长度*/ }SeqList; void main() { SeqList L; int i,x; int n=10; /*欲建立的顺序表长度*/ L.length=0; void CreateList(SeqList *L,int n); void PrintList(SeqList L,int n); int LocateList(SeqList L,DataType x); void InsertList(SeqList *L,DataType x,int i); void DeleteList(SeqList *L,int i); CreateList(&L,n); /*建立顺序表*/ PrintList(L,n); /*打印顺序表*/ printf("输入要查找的值："); scanf("%d",&x); i=LocateList(L,x); /*顺序表查找*/ printf("输入要插入的位置："); scanf("%d",&i); printf("输入要插入的元素："); scanf("%d",&x);

线性表的创建插入和删除的操作

实验容：线性表的创建、插入删除等 #include"stdio.h" #include"stdlib.h" int*inistl(int m,int *n) /*建立线性表函数*/ {int*v=NULL; v=malloc(m*sizeof(int*)); /*创建链表，并把首地址赋给指针V*/ n=0; return v; } void insl(int*v,int m,int*n,int i,int b)/*在链表指定位置插入元素b*/ { int j; if(*n>=m) /*检查是否链表溢出*/ {printf("the stack is overflow\n"); return; } if(i>*n-1) i=*n+1; /*若插入点大于元素位置则在表的结束插入*/ if(i<1) i=1; /*空表在首部插入元素*/ for(j=*n;j>=i;j--) /*首位之间任意位置的插入*/ v[j]=v[j-1]; v[i-1]=b; *n=*n+1; /*插入后元素统计指针加1*/ } void desl(int*v,int m,int*n,int i) /*线性表删除函数*/ {int j; if(*n==0) /*判断线性表是否为空*/ {printf("the stack is underflow\n "); return; } if((i<1)||(i>*n)) /*删除点在首部以前和尾部以后特殊情况排除*/ {printf("not this element in the list!"); return; } for (j=i;j<=*n-1;j++) /*在允许位置做删除操作*/ v[j-1]=v[j]; *n=*n-1; /*元素统计指针减1*/ return; }) void input(int*v,int n) /*空表起始输入元素函数*/ {int i; for(i=0;i

单链表的初始化,建立,插入,查找,删除

单链表的初始化，建立，插入，查找，删除。 #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.实验目的和要求： 1）了解顺序表的基本概念、顺序表结构的定义及在顺序表上的基本操作(插入、删除、查找以及线性表合并)。 2)通过在Turbo C（WinTc，或visual stdio6）实现以上操作的C语言代码。 3）提前了解实验相关的知识（尤其是C语言）。 3.实验内容：(二选一) 1)顺序表的插入算法,删除算法,顺序表的合并算法 2)与线性表应用相关的实例(自己选择详尽实例) 4.部分参考实验代码： ⑴顺序表结构的定义： #include #define MAXLEN 255 typedef int ElemType; typedef struct { ElemType elem[MAXLEN]; int length; }sqList; ⑵顺序表前插（在第i号元素前插入一个新的元素） int ListInsert(sqList *la,int i,int x)

{ int j; if(i<0||i>la-> length +1) {printf(“\n the value of i is wrong!”); return 0; } if(la-> length +1>=MAXLEN) { printf(“\n overflow!”); return 0; } . for(j=la-> length;j>=i;j--) la->list[j+1]=la->list[j]; la->list[i]=x; la-> length++; return 1; } ⑶顺序表删除 int ListDelete(sqList *la,int i) { if(i<0||i>la-> length) { printf(“\n the position is wrong!\n”); return 0; }

数据结构-线性表输入-输出-插入-删除-查找

数据结构-线性表输入-输出-插入-删除-查找

创建一个线性表实现输入，输出，插入，删除，定位。 （注意：不论在调用哪个函数前，都要先使L.elem=a，就是使指针elem回到数组a的首地址。） #include #include #include #define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 #define LISTINCREMENT 10 //线性表存储空间的分配增量 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int ElemType; //接下来ElemType代表的就是int typedef int Status; //Status也代表int int i,*p,*q; //p，q都是指针类型 ElemType e; typedef struct { ElemType *elem; //定义成指针类型//存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位) }SqList; //***********************构建空的线性表*************************// Status InitList_Sq(SqList &L) //构建一个空的线性表L { L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); //存储分配失败 L.length=0; //空表长度为0 L.listsize=LIST_INIT_SIZE; //初始存储容量 return OK; } //**************************线性表输入函数*********************// void input(SqList &L) //输入函数 { scanf("%d",L.elem); //要先输入一个，不然一开始就是0，无法进行循环while(*L.elem) // 加*是因为elem是指针，加之后才代表值{ L.elem++; //输入后指针后移 L.length++; //表长加1 scanf("%d",L.elem); //循环中也要再输入 } } //**************************线性表打印函数********************// void print(SqList &L) //输出函数

线性表的插入与删除的实现

线性表的插入与删除的实现 一.算法的基本概念 计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。 1.算法的基本特征：可行性，确定性，有穷性，拥有足够的情报。 2.算法的基本要素：算法中对数据的运算和操作、算法的控制结构。 3.算法设计的基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。 4.算法设计的要求：正确性、可读性、健壮性、效率与低存储量需求 三.数据结构的定义 1.数据的逻辑结构：反映数据元素之间的关系的数据元素集合的表示。数据的逻辑结构包括集合、线形结构、树形结构和图形结构四种。 2.数据的存储结构：数据的逻辑结构在计算机存储空间种的存放形式称为数据的存储结构。常用的存储结构有顺序、链接、索引等存储结构。 在数据结构中，没有前件的结点称为根结点；没有后件的结点成为终端结点。插入和删除是对数据结构的两种基本运算。还有查找、分类、合并、分解、复制和修改等。 五.线性结构和非线性结构 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构和非线性结构。 线性结构：非空数据结构满足：有且只有一个根结点；每个结点最多有一个前件，最多只有一个后件。非线性结构：如果一个数据结构不是线性结构，称之为非线性结构。 常见的线性结构：线性表、栈、队列 七.线性表的顺序存储结构 线性表的顺序表指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构具备如下两个基本特征： 1.线性表中的所有元素所占的存储空间是连续的； 2.线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 即线性表逻辑上相邻、物理也相邻，则已知第一个元素首地址和每个元素所占字节数，则可求出任一个元素首地址。 假设线性表的每个元素需占用K个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系: LOC(ai+1)=LOC(ai)+K LOC(ai)=LOC(a1)+(i-1)*K ① 其中，LOC(a1)是线性表的第一个数据元素a1的存储位置，通常称做线性表的起始位置或基地址。 因为在顺序存储结构中，每个数据元素地址可以通过公式①计算得到，所以线性表的顺序存储结构是随机存取的存储结构。 在线性表的顺序存储结构下，可以对线性表做以下运算： 插入、删除、查找、排序、分解、合并、复制、逆转

C语言链表的建立、插入和删除

数组作为存放同类数据的集合，给我们在程序设计时带来很多的方便，增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定，不能在程序中进行调整，这样一来，在程序设计中针对不同问题有时需要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) 找到表头。

数据结构循环链表插入和删除源代码代码

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&&jnext; ++j; }//寻找第i-1个节点 if(!P||j>i-1) return ERROR; S=(CrLinklist)malloc(sizeof(CrLNode));//生成新节点 S->data=e; S->next=P->next;//插入到S中 P->next=S; return L; } CrLinklist ListDelete_L(CrLinklist L,int i)//单链表的删除 { CrLinklist P,S;

线性表的插入,删除,修改

#include"stdio.h" #include"stdlib.h" int*inistl(int m,int *n) /*建立线性表函数*/ {int*v=NULL; v=malloc(m*sizeof(int*)); /*创建链表，并把首地址赋给指针V*/ n=0; return v; } void insl(int*v,int m,int*n,int i,int b)/*在链表指定位置插入元素b*/ { int j; if(*n>=m) /*检查是否链表溢出*/ {printf("the stack is overflow\n"); return; } if(i>*n-1) i=*n+1; /*若插入点大于元素位置则在表的结束插入*/ if(i<1) i=1; /*空表在首部插入元素*/ for(j=*n;j>=i;j--) /*首位之间任意位置的插入*/ v[j]=v[j-1]; v[i-1]=b; *n=*n+1; /*插入后元素统计指针加1*/ } void desl(int*v,int m,int*n,int i) /*线性表删除函数*/ {int j; if(*n==0) /*判断线性表是否为空*/ {printf("the stack is underflow\n "); return; } if((i<1)||(i>*n)) /*删除点在首部以前和尾部以后特殊情况排除*/ {printf("not this element in the list!\n"); return; } for (j=i;j<=*n-1;j++) /*在允许位置做删除操作*/ v[j-1]=v[j]; *n=*n-1; /*元素统计指针减1*/ return; } void input(int*v,int n) /*空表起始输入元素函数*/ {int i; for(i=0;i

数据结构--单链表的插入和删除

单链表的插入和删除实验日志 指导教师刘锐实验时间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(); //函数，按值查找结点

线性表顺序存储实现、插入、删除操作

#include #include #define list_init_size 100 #define listincrement 10 #define ok 1 #define overflow -1 #define elemtype int #define error -1 elemtype *q; elemtype *p; typedef struct{ elemtype *elem; int length; int listsize; }sqlist; int initlist_sq(sqlist &l)//线性表动态分配存储结构// { l.elem=(elemtype*)malloc(list_init_size*sizeof(elemtype)); if(!l.elem) { cout<<"the list have no space"<>m;

单链表的插入和删除实验报告

. 实验一、单链表的插入和删除 一、目的 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 二、要求： 建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。 三、程序源代码 #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); //删除所有结点，释放内存 } //==========用尾插入法建立带头结点的单链表

实验一数据结构顺序表的插入和删除

实验一顺序表的操作 1. 实验题目：顺序表的操作 2.实验目的和要求： 1)了解顺 序表的基本概念、顺序表结构的定义及在顺序表上的基本操作(插入、 删除、查找以及线性表合并 )。 2)通过在 Turbo C ( WinTc ，或 visual stdio6 )实现以上操作的 C 语言 代码。 3)提前了解实验相关的知识(尤其是 C 语 言)。 3.实验内容：(二选一) 1) 顺序表的插入算法, 删除算法, 顺序表的合并算法 2) 与线性表应用相关的实例( 自己选择具体实例) 4.部分参考实验代码： ⑴ 顺序表结构的定义： #include #define MAXLEN 255 typedef int ElemType; typedef struct { ElemType elem[MAXLEN]; int length; }sqList; ⑵ 顺序表前插(在第i 号元素前插入一个新的元素) int ListInsert(sqList *la,int i,int x) { int j; if(i<0||i>la-> length +1) { printf( “ n the value of i is wrong! ” ); return 0; } if(la-> length +1>=MAXLEN) { printf( “ n overflow! ” ); return 0; }

. for(j=la-> length;j>=i;j--) la->list[j+1]=la->list[j]; la->list[i]=x; la-> length ++; return 1; } ⑶ 顺序表删除 int ListDelete(sqList *la,int i) { if(i<0||i>la-> length ) { printf( “ return 0; n”); } for(i;i length;i++) la->list[i-1]=la->list[i]; la-> length --; return 1; } 5.附录：实验预备知识： ⑴ 复习 C 语言中数组的用法。 ⑵ 了解线性表和顺序表的概念，顺序表的定义方法； 线性表是n 个数据元素的有限序列，至于每个数据元素的具体含义，在不同的情况下各不相同。 顺序表是线性表的顺序存储表示，是用一组地址连续的存储单元依次存储线性表的数据元素。 在 C 语言中，顺序表是用数组来实现的。 ⑶ 掌握线性表在顺序存储结构上实现基本操作：查找、插入、删除和 合并的算法。 在实现这些算法的时候，要注意判断输入数据的合法性，除此之外还要要注意以下内容： 在实现查找的时候，首先要判断该顺序表是否为空，其次要判断查找后的结果（查到时输出查到的数据，未查到时给出未查到提 示）。 在实现插入的时候，首先要判断该顺序表是否为满，如为满则报错 （此时要注意：顺序表是用数组来实现的，它不能随机分配空 间）；如不为满，则需判断要插入的位置是否合法（例如：如果 一个线性表的元素只有10 个，而要在第0 个元素前插入或在第 11 个元素后插入就为不合法）。其次要注意是前插还是后插，两

线性表的插入和删除

实验一线性表的基本操作 一、实验目的 掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构上的运算。 二、实验要求 1、认真阅读和掌握本实验的程序。 2、上机运行本程序。 3、保存和打印出程序的运行结果，并结合程序进行分析。 4、按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单 和运行结果 三、实验内容 线性表基本操作的实现。 算法描述:对每一个算法,要写出算法的中文描述。本实验中要求写出在第i 个结点前插入数据为x的结点、删除指定结点、创建一个线性表、打印线性表的算法描述。 四、程序清单 1、sqlist.h文件清单： #include "stdio.h" #include "malloc.h" #define null 0 #define maxsize 1024 typedef char datatype; typedef struct { datatype data[maxsize]; int last; }sequenlist; /*在第i个结点前插入元素x（note：元素从0始计数）*/ int insert(sequenlist *L, datatype x,int i) { int j; if (L->last==maxsize-1)/*如果原线性表已经满了*/ { printf("overflow"); return 0; } else if ((i<0)||(i>L->last)) /*如果输入的i值超出范围*/ { printf("error,please input the right 'i'"); return 0; } else { for(j=L->last; j>=i; j--) /*从第i个元素起,每个元素后移一位*/ L->data[j+1]=L->data[j];

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

实验报告 课程名称数据结构 姓名 学号 专业班级 指导教师

目录 第二章线性表的查找、插入、删除 (1) 1.1顺序表的查找 (1) 1.2顺序表的插入 (2) 1.3顺序表的删除 (4) 单链表的建立、插入、删除 (6) 2.1 单链表的建立（尾插法） (6) 2.2 单链表的插入 (8) 2.3 单链表的删除 (10) 第三章栈 (14) 3.1链栈 (14) 3.2 顺序栈 (16) 3.3队列 (18) 3.4杨辉三角 (20) 第四章串 (23) 4.1字符串的建立 (23) 4.2顺序串的插入 (25)

1.线性表的查找、插入、删除 1.1顺序表的查找 程序： #include #include #include #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define ElemType int #define MAXSIZE 100 /*此处的宏定义常量表示线性表可能达到的最大长度*/ typedef struct { ElemType elem[MAXSIZE]; /*线性表占用的数组空间*/ int last; /*记录线性表中最后一个元素在数组elem[]中的位置（下标值），空表为-1*/ }Seqlist; int Locate(Seqlist L,ElemType e) /*在顺序表L中查找与e相等的元素，若L。elem[i]=e,则找到该元素，并返回i+1，若找不到，则返回-1*/ { int i=0; /*i为扫描计数器，初值为0，即从第一个元素开始比较*/ while ((i<=https://www.doczj.com/doc/df12923927.html,st)&&(L.elem[i]!=e)) /*顺序扫描表，直到找到值为e的元素，或扫描到表尾仍没找到*/ i++; if(i<=https://www.doczj.com/doc/df12923927.html,st) return (i+1); /*若找到值为e的元素，则返回其序号*/ else return(-1); /*若没找到，则返回空序号*/ } void main() { Seqlist l; int p,q,r; int i; printf("请输入线性标的长度:"); scanf("%d",&r);