线性表的插入和删除C++程序

C语⾔——线性表及其应⽤程序要求1.建⽴含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。

2.利⽤前⾯的实验先建⽴⼀个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插⼊元素68。

3.建⽴⼀个带头结点的单链表，结点的值域为整型数据。

要求将⽤户输⼊的数据按尾插⼊法来建⽴相应单链表。

输⼊和输出的格式1.顺序线性表的建⽴、插⼊及删除顺序表#include<stdio.h>#include<stdlib.h>#define ListSize 50typedef int DataType;//线性表的顺序存储⽅式typedef struct {DataType data[ListSize];int l;}SeqList;//创建顺序线性表void CreateList(SeqList *A,int n){int i;for(i=0;i<n;i++){scanf("%d",&(A->data[i]));}A->l=n;}//在顺序线性表中插⼊某个元素void InsertList(SeqList *A,DataType x,int i){int j;if(i<1 || i>A->l) //插⼊时的条件{printf("插⼊位置错误!\n");exit(0);}else{printf("插⼊成功!\n");}if(A->l >= ListSize){printf("列表溢出!\n");exit(0);}for(j=A->l-1;j>=i-1;j--){A->data[j+1]=A->data[j]; //插⼊时，把各个元素向后移动后，然后在进⾏插⼊}A->data[i-1]=x;A->l++;}//在顺序线性表中删除某个元素void DeleteList(SeqList *A,int i){int j;if(A->l==0) //删除时的条件{printf("列表为空!\n");exit(0);}if(i<1 || i>A->l){printf("删除位置错误!\n\n");exit(0);}for(j=i;j<=A->l-1;j++) //删除时，把各个元素向前移动，覆盖掉要删除的元素{A->data[j-1]=A->data[j];}A->l--;}//输出线性表void DisList(SeqList *L){int i;for(i=0;i<L->l;i++)printf("%d ",L->data[i]);printf("\n");}void main(){SeqList *A=(SeqList*)malloc(sizeof(SeqList));int a=7;printf("请输⼊7个整型元素:\n");CreateList(A,a);printf("输出SeqList的长度: \n");printf("长度=%d\n",A->l);printf("表内元素为");DisList(A);DataType x;printf("请输⼊需要插⼊的元素的位置!\n");int i;scanf("%d",&i);printf("请输⼊需要插⼊的元素!\n");scanf("%d",&x);InsertList(A,x,i);printf("长度=%d\n",A->l);printf("表内元素为");DisList(A);printf("请输⼊需要删除的元素的位置!\n");scanf("%d",&i);DeleteList(A,i);printf("表内元素为");DisList(A);printf("长度=%d\n",A->l);}输⼊和输出的格式顺序表输⼊输出：定义输⼊7个整型元素，回车进⾏插⼊和删除，输出线性表2.链式线性表的建⽴、插⼊及删除单链表#include <stdio.h>#include <stdlib.h>typedef int ElemType;//定义结点类型typedef struct Node{ElemType data; //单链表中的数据域struct Node *next; //单链表的指针域}Node,*LinkedList;//单链表的初始化LinkedList LinkedListInit(){Node *A;A = (Node *)malloc(sizeof(Node)); //申请结点空间if(A == NULL) //判断是否有⾜够的内存空间printf("申请内存空间失败\n");A->next = NULL; //将next设置为NULL,初始长度为0的单链表return A;}//单链表的建⽴LinkedList LinkedListCreat(){Node *A;A = (Node *)malloc(sizeof(Node)); //申请头结点空间A->next = NULL; //初始化⼀个空链表Node *r;r = A;ElemType x;while(scanf("%d",&x) != EOF){Node *p;p = (Node *)malloc(sizeof(Node));p->data = x;r->next = p;r = p;}r->next = NULL;return A;}//单链表的插⼊，在链表的第i个位置插⼊x的元素LinkedList LinkedListInsert(LinkedList A,int i,ElemType x){Node *pre; //pre为前驱结点pre = A;int tempi = 0;for (tempi = 1; tempi < i; tempi++)pre = pre->next; //查找第i个位置的前驱结点Node *p; //插⼊的结点为pp = (Node *)malloc(sizeof(Node));p->data = x;p->next = pre->next;pre->next = p;return A;}//单链表的删除，在链表中删除数据值为x的元素LinkedList LinkedListDelete(LinkedList A,ElemType x){Node *p,*pre; //pre为前驱结点，p为查找的结点。

实验01 线性表的基本操作一、实验目的1. 了解线性表的结构特点及有关概念；2. 理解线性表的存储结构；3. 掌握顺序表及单链表的基本操作算法。

二、实验内容1、编写程序实现顺序表的各种基本运算：初始化、插入、删除、取表元素、求表长、输出表、销毁、判断是否为空表、查找元素。

在此基础上设计一个主程序完成如下功能：（1）初始化顺序表L；（2）依次在表尾插入a，b，c，d，e五个元素；（3）输出顺序表L；（4）输出顺序表L的长度；（5）判断顺序表L是否为空；（6）输出顺序表L的第4个元素；（7）输出元素c的位置；（8）在第3个位置上插入元素f，之后输出顺序表L；（9）删除L的第2个元素，之后输出顺序表L；（10）销毁顺序表L。

2、编写程序实现单链表的各种基本运算：初始化、插入、删除、取表元素、求表长、输出表、销毁、判断是否为空表、查找元素。

在此基础上设计一个主程序完成如下功能：（1）初始化单链表L；（2）依次在表尾插入a，b，c，d，e五个元素；（3）输出单链表L；（4）输出单链表L的长度；（5）判断单链表L是否为空；（6）输出单链表L的第4个元素；（7）输出元素c的位置；（8）在第3个位置上插入元素f，之后输出单链表L；（9）删除L的第2个元素，之后输出单链表L；（10）销毁单链表L。

三、实验要点及说明一．顺序表1.顺序表初始化:(1)为顺序表L动态分配一个预定大小的数组空间，使elem 指向这段空间的基地址。

(2)将表的当前长度设为0.2.顺序表的取值:(1)判断指定的位置序号i值是否合理（1<=i<=L.length），若不合理则返回ERROR.(2)若i值合理，则将i个数据元素L.elem[i]赋给参数e,通过e返回第i个数据元素的传值。

3.顺序表的查找:(1)从第一个元素起，依次和e相比较，若找到与e相等的元素L.elem[i]，则查找成功，返回该元素的序号i+1.(2)若查遍整个顺序表都没要找到，则查找失败，返回0.4．顺序表的插入:(1)判断插入位置i是否合法(i值的合法范围是1<=i<=n+1)，若不合法则返回值ERROR.(2)判断顺序表的存储空间是否已满，若满则返回值ERROR(3)将第n个至第i个位置的元素依次向后移动一个位置，空出第i个位置(i=n+1时无需移动)。

实验二线性表的基本操作一、实验目的1．掌握用C++/C语言调试程序的基本方法。

2．掌握线性表的顺序存储和链式存储的基本运算，如插入、删除等.二、实验要求1．C++/C完成算法设计和程序设计并上机调试通过.2．撰写实验报告，提供实验结果和数据。

3．分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。

三、实验内容:1。

分析并运行以下各子程序的主要功能。

程序1:顺序存储的线性表和运算#include<stdio。

h>#define MAXSIZE 100int list［MAXSIZE］;int n；/*insert in a seqlist＊/int sq_insert(int list[]， int *p_n， int i， int x)｛int j；if （i〈0 || i>＊p_n） return(1）;if (＊p_n==MAXSIZE) return(2）；for （j=＊p_n+1; j〉i; j——）list［j］=list[j-1];list［i]=x;（*p_n）++;return（0);｝/*delete in a seq list*/int sq_delete(int list[］, int ＊p_n, int i）｛int j；if （i〈0 |｜ i>=＊p_n） return(1)；for （j = i+1; j〈=＊p_n； j++)list［j-1] = list[j];（＊p_n）—-;return（0)；}void main(）{int i，x,temp;printf（”please input the number for n\n”);printf（"n=”);scanf（"％d",＆n)；for （i=0； i<=n； i++)｛printf(”list［%d］=",i)；scanf（”％d",＆list[i］)；｝printf（”The list before insertion is\n”);for (i=0; i<=n； i++） printf(”%d ",list［i］);printf(”\n”）;printf（”please input the position where you want to insert a value\nposition=”)；scanf(”%d",＆i）;printf(”please input the value you want to insert。

一、实验目的和要求通过对顺序表的编程练习，加强对顺序表的特点、顺序存储结构及其基本运算的理解和掌握。

提前了解实验相关的c语言的知识。

使用C语言根据相应算法编写一个程序，实现建立线性顺序表、插入和删除等基本操作。

要求仔细阅读下面的内容，编写一个C程序，上机调试通过，并观察其结果，写出实验报告书。

二、实验内容和原理内容：建立一个容量10的顺序表，在其中插入3个元素，然后作删除运算。

原理：在第i个元素前插入元素，从第i个元素开始到最后一个元素均向后移动一个位置，然后将新元素插入到第i个位置，将线性表的长度加1。

删除第i个元素，从第i+1个元素开始到最后一个元素均向前移动一个位置，然后将线性表的长度减1。

三、主要仪器设备计算机一台四、实验主程序#include<stdio.h>#include<stdlib.h>struct List{int size;int n;int *head;};void init(struct List *pl,int size){pl->size=size;pl->n=0;pl->head=malloc(size*sizeof(int)); }void in(int i,int val,struct List *pl){int k;if(pl->n==pl->size){printf("list is full.\n");return;}if(i>pl->n)i=pl->n+1;if(i<1)i=1;for(k=pl->n-1;k>=i-1;--k)pl->head[k+1]=pl->head[k];pl->head[i-1]=val;++pl->n;}void out(int i,struct List *pl){int k;if(pl->n==0){printf("list is empty.\n");return;}if(i<1||i>pl->n){printf("this element is not in the list.\n");return;}for(k=i;k<=pl->n;++k)pl->head[k-1]=pl->head[k];--pl->n;return;}void print(const struct List *pl) {int i;for(i=0;i!=pl->n;++i)printf("%d ",pl->head[i]);printf("\n");}int main(void){int i;struct List list;init(&list,10);for(i=0;i!=5;++i)in(i+1,i,&list);print(&list);in(1,5,&list);print(&list);in(10,4,&list);print(&list);in(5,50,&list);print(&list);out(1,&list);print(&list);out(list.n,&list);print(&list);out(3,&list);print(&list);getchar();return 0;}实验结果五、实验心得通过实验学习，我理解了线性顺序表的插入与删除的算法，了解到线性顺序表的插入与删除得效率低下，感到受益匪浅。

线性表的查找、插⼊、删除运算#include "seqlist.h"int main(){ int a=5,b=4;cout<<"LObj.IsEmpty(): "<<LObj.IsEmpty()<<endl;cout<<"LObj.Length(): "<<LObj.Length()<<endl;LObj.Insert(-1,0);LObj.Insert(0,1);LObj.Insert(1,2);LObj.Insert(2,3);LObj.Insert(3,4);LObj.Insert(4,5);LObj.Insert(5,6);LObj.Insert(6,7);LObj.Insert(7,8);LObj.Insert(8,9);LObj.Insert(9,10);LObj.Insert(10,11);LObj.Output(cout);cout<<"LObj.Find(1,a):"<<LObj.Find(1,a)<<endl;cout<<"LObj.Search(b):"<<LObj.Search(b)<<endl;cout<<"LObj.Delete(5):"<<LObj.Delete(5);LObj.Output(cout);cout<<"Here end OK."<<endl;}#include "linearlist.h"const int SIZE=20;template <class T>class SeqList:public LinearList<T>{ public:SeqList(int mSize);~SeqList() { delete [] elements; }bool IsEmpty() const;int Length() const;bool Find(int i,T& x) const;int Search(T x) const;bool Insert(int i,T x);bool Delete(int i);bool Update(int i,T x);void Output(ostream& out)const ;private:int maxLength,n; //顺序表的最⼤长度T *elements; //动态⼀维数组的指针};SeqList<int> LObj(SIZE); //定义了⼀个有5个整型值的顺序表对象template <class T>SeqList<T>::SeqList(int mSize){maxLength=mSize;elements=new T[maxLength];n=0;}template <class T>bool SeqList<T>::IsEmpty() const{return n==0;}template <class T>int SeqList<T>::Length() const{return n;}template <class T>bool SeqList<T>::Find(int i,T& x) const{if(i<0||i>n-1){cout<<"Out of Bounds"<<endl;}x=elements[i];return true;}template <class T>int SeqList<T>::Search(T x) const{for(int j=0;j<n;j++)if(elements[j]==x) return j;return -1;}template <class T>bool SeqList<T>::Insert(int i,T x){if(i<-1||i>n-1){cout<<"Out of pounds"<<endl; return false; }if(n==maxLength){cout<<"OverFlow"<<endl; return false;}for(int j=n-1;j>i;j--) elements[j+1]=elements[j]; elements[i+1]=x;n++; return true;}template <class T>bool SeqList<T>::Delete(int i){if(!n){cout<<"UnderFlow"<<endl; return false;}if(i<0||i>n-1){cout<<"Out of Bounds"<<endl; return false; }for(int j=i+1;j<n;j++) elements[j-1]=elements[j]; n--; return true;}template <class T>bool SeqList<T>::Update(int i,T x){if(i<0||i>n-1){cout<<"Out of Bounds"<<endl; return false; }elements[i]=x;return true;}template <class T>void SeqList<T>::Output(ostream& out) const{for(int i=0;i<n;i++) out<<elements[i]<<"";cout<<endl;}#include <iostream>using namespace std;template <class T>class LinearList{ public:virtual bool IsEmpty() const=0;virtual int Length() const=0;virtual bool Find(int i,T& x) const=0;virtual int Search(T x) const=0;virtual bool Insert(int i,T x)=0;virtual bool Delete(int i)=0;virtual bool Update(int i,T x)=0;virtual void Output(ostream& out)const=0; protected:int n; //线性表的长度};。

实验一线性表的基本操作一、实验目的与基本要求1．掌握数据结构中的一些基本概念。

数据、数据项、数据元素、数据类型和数据结构，以及它们之间的关系。

2．了解数据的逻辑结构和数据的存储结构之间的区别与联系；数据的运算与数据的逻辑结构的关系。

3．掌握顺序表和链表的基本操作：插入、删除、查找以及表的合并等运算。

4．掌握运用C语言上机调试线性表的基本方法。

二、实验条件1．硬件：一台微机2．软件：操作系统和C语言系统三、实验方法确定存储结构后，上机调试实现线性表的基本运算。

四、实验内容1．建立顺序表，基本操作包括：初始化，建立一个顺序存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。

2．建立单链表，基本操作包括：初始化，建立一个链式存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。

3．假设有两个按数据元素值非递减有序排列的线性表A和B，均以顺序表作为存储结构。

编写算法将A表和B表归并成一个按元素值非递增有序（允许值相同）排列的线性表C。

（可以利用将B中元素插入A中，或新建C表）4．假设有两个按数据元素值非递减有序排列的线性表A和B，均以单链表作为存储结构。

编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C。

五、附源程序及算法程序流程图1.源程序（1）源程序(实验要求1和3)#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct arr{int * elem;int length;int listsize;}Sqlist;void menu(); //菜单void InitList(Sqlist *p); // 创建线性表void ShowList(Sqlist *p); // 输出顺序线性表void ListDelete(Sqlist *p,int i,int &e); // 在顺序线性表中删除第i个元素，并用e返回其值void ListInsert(Sqlist *p); // 在顺序线性表中第i个元素前插入新元素evoid ListEmpty(Sqlist *p); // 判断L是否为空表void GetList(Sqlist *p,int i,int &e); // 用e返回L中第i个数据元素的值void ListInsert(Sqlist *p,int i,int e);bool compare(int a,int b);void LocateElem(Sqlist *L,int e); // 在顺序线性表L中查找第1个值与e满足compare()d元素的位序void MergeList_L(Sqlist *La,Sqlist *Lb); // 归并void main(){Sqlist La;Sqlist Lb;int n,m,x;menu();scanf("%d",&n);while(n){switch(n){case 0: ; break;case 1:InitList(&La);break;case 2:ListEmpty(&La);break;case 3:printf("请输入插入的位序:\n");scanf("%d",&m);printf("请出入要插入的数:\n");scanf("%d",&x);ListInsert(&La,m,x);break;case 4:printf("请输入删除元素的位序:\n");scanf("%d",&m);ListDelete(&La,m,x);printf("删除的元素为:%d\n",x);break;case 5:printf("请输入要找的与线性表中相等的数:\n");scanf("%d",&m);LocateElem(&La,m);break;case 6:printf("请输入查找的位序:\n");scanf("%d",&m);GetList(&La,m,x);printf("La中第%d个元素的值为%d\n",m,x);break;case 7:ShowList(&La);break;case 8:InitList(&Lb);break;case 9:MergeList_L(&La,&Lb);printf("归并成功!");break;}menu();scanf("%d",&n);}}/*菜单*/void menu(){printf("********************\n\n");printf(" 0.退出\n\n");printf(" 1.创建线性表La\n\n");printf(" 2.判断La是否为空表\n\n");printf(" 3.插入元素(La)\n\n");printf(" 4.删除元素(La)\n\n");printf(" 5.定位元素(La)\n\n");printf(" 6.取元素(La)\n\n");printf(" 7.输出线性表\n\n");printf(" 8.创建线性表Lb\n\n");printf(" 9.归并为一个线性表La\n\n");printf("********************\n\n");}/*创建顺序线性表L*/void InitList(Sqlist *L){int n;int i=0;L->elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));if(NULL==L->elem)printf("储存分配失败!\n");else{L->length=0;L->listsize=LIST_INIT_SIZE;printf("输入顺序表a:\n");scanf("%d",&n);while(n){L->elem[i]=n;i++;L->length++;L->listsize=L->listsize-4;scanf("%d",&n);}}}/*输出顺序线性表*/void ShowList(Sqlist *p){int i;if(0==p->length)printf("数组为空!\n");elsefor(i=0;i<p->length;i++)printf("%d ",p->elem[i]);printf("\n");}/*判断L是否为空表*/void ListEmpty(Sqlist *p)if(0==p->length)printf("L是空表!\n");elseprintf("L不是空表!\n");}/*在顺序线性表中第i个元素前插入新元素e */void ListInsert(Sqlist *p,int i,int e){int *newbase;int *q1;int *q2;while(i<1||i>p->length+1){printf("您输入的i超出范围!\n请重新输入要插入的位置\n:");scanf("%d",&i);}if(p->length>=p->listsize){newbase=(int *)realloc(p->elem,(p->listsize+LISTINCREMENT)*sizeof(int));if(!newbase)exit(0);else{p->elem=newbase;p->listsize+=LISTINCREMENT;}}q1=&(p->elem[i-1]);for(q2=&(p->elem[p->length-1]);q2>=q1;--q2)*(q2+1)=*q2;*q1=e;++p->length;}/*/在顺序线性表中删除第i个元素，并用e返回其值*/void ListDelete(Sqlist *p,int i,int &e){int *q1,*q2;while(i<1||i>p->length){printf("您输入的i超出范围!请重新输入:");scanf("%d",&i);}q1=&(p->elem[i-1]);e=*q1;q2=p->elem+p->length-1;for(++q1;q1<=q2;++q1)*(q1-1)=*q1;--p->length;}/*对比a与b相等*/bool compare(int a,int b){if(a==b)return 1;elsereturn 0;}/*在顺序线性表L中查找第1个值与e满足compare()d元素的位序*/ void LocateElem(Sqlist *L,int e){int i=1;int *p;p=L->elem;while(i<=L->length && !compare(*p++,e))++i;if(i<=L->length)printf("第1个与e相等的元素的位序为%d\n",i);elseprintf("没有该元素!\n");}/*用e返回L中第i个数据元素的值*/void GetList(Sqlist *p,int i,int &e){Sqlist *p1;p1=p;e=p1->elem[i-1];}/* 已知顺序线性表La和Lb是元素按值非递减排列*//* 把La和Lb归并到La上,La的元素也是按值非递减*/void MergeList_L(Sqlist *La,Sqlist *Lb){int i=0,j=0,k,t;int *newbase;Sqlist *pa,*pb;pa=La;pb=Lb;while(i<pa->length && j<pb->length){if(pa->elem[i] >= pb->elem[j]){if(pa->listsize==0){newbase=(int*)realloc(pa->elem,(pa->listsize+LISTINCREMENT)*sizeof(int));if(!newbase)exit(0);}for(k=pa->length-1; k>=i; k--)pa->elem[k+1]=pa->elem[k];pa->length++;pa->elem[i]=pb->elem[j];i++;j++;}elsei++;}while(j<pb->length){if( pa->listsize < pb->length-j ){newbase=(int*)realloc(pa->elem,(pa->listsize+LISTINCREMENT)*sizeof(int));if(!newbase)exit(0);}for(j;j<pb->length;j++,i++){pa->elem[i]=pb->elem[j];pa->length++;}}for(i=0;i<pa->length/2;i++){t=pa->elem[i];pa->elem[i]=pa->elem[pa->length-i-1];pa->elem[pa->length-i-1]=t;}}（2）源程序(实验要求2和4)#include<stdio.h>#include<malloc.h>#include<stdlib.h>typedef struct LNode{int data;struct LNode *next;}LNode, *LinkList;void menu();LinkList InitList();void ShowList(LinkList L);void ListDelete(LinkList L,int i,int &e);void ListEmpty(LinkList L);void GetList(LinkList L,int i,int &e);void ListInsert(LinkList L,int i,int e);bool compare(int a,int b);void LocateElem(LinkList L,int e);LinkList MergeList_L(LinkList La,LinkList Lb);int total=0;void main(){LinkList La;LinkList Lb;La=(LinkList)malloc(sizeof(struct LNode));La->next=NULL;Lb=(LinkList)malloc(sizeof(struct LNode));Lb->next=NULL;int n;int m;int x;menu();scanf("%d",&n);while(n){switch(n){case 0: ; break;case 1:La->next=InitList();break;case 2:ListEmpty(La);break;case 3:printf("请输入要插入到第几个节点前:\n");scanf("%d",&m);printf("请输入插入的数据:\n");scanf("%d",&x);ListInsert(La,m,x);break;case 4:printf("请输入删除元素的位序:\n");scanf("%d",&m);ListDelete(La,m,x);printf("删除的元素为:%d\n",x);break;case 5:printf("请输入要找的与线性表中相等的数:\n");scanf("%d",&m);LocateElem(La,m);break;case 6:printf("请输入查找的位序:\n");scanf("%d",&m);GetList(La,m,x);printf("La中第%d个元素的值为%d\n",m,x);break;case 7:ShowList(La);break;case 8:Lb->next=InitList();break;case 9:La=MergeList_L(La,Lb);printf("归并成功\n");break;}menu();scanf("%d",&n);}}void menu(){printf("********************\n\n");printf(" 0.退出\n\n");printf(" 1.创建线性表La\n\n");printf(" 2.判断是否为空表\n\n");printf(" 3.插入元素\n\n");printf(" 4.删除元素\n\n");printf(" 5.定位元素\n\n");printf(" 6.取元素\n\n");printf(" 7.输出线性表\n\n");printf(" 8.创建线性表Lb\n\n");printf(" 9.归并两线性表\n\n");printf("********************\n\n");}// 创建链式线性表LLinkList InitList(){int count=0;LinkList pHead=NULL;LinkList pEnd,pNew;pEnd=pNew=(LinkList)malloc(sizeof(struct LNode));printf("请输入数据:\n");scanf("%d",&pNew->data);while(pNew->data){count++;if(count==1){pNew->next=pHead;pEnd=pNew;pHead=pNew;}else{pNew->next=NULL;pEnd->next=pNew;pEnd=pNew;}pNew=(LinkList)malloc(sizeof(struct LNode));printf("请输入数据:\n");scanf("%d",&pNew->data);}free(pNew);total=total+count;return pHead;}// 判断L是否为空表void ListEmpty(LinkList L){if(NULL==L->next)printf("此表为空表!\n");elseprintf("此表不为空表!\n");}// 在链式线性表中第i个元素前插入新元素e void ListInsert(LinkList L,int i,int e){LinkList p;LinkList s;p=L;int j=0;while(p&&j<i-1){p=p->next;++j;}if(!p||j>i-1)printf("不存在您要找的节点!\n");else{s=(LinkList)malloc(sizeof(int));s->data=e;s->next=p->next;p->next=s;printf("插入节点成功!\n");}}// 输出链式线性表void ShowList(LinkList L){LinkList p;p=L->next;if(p==NULL)printf("此表为空表!\n");elsewhile(p){printf("%d ",p->data);p=p->next;}printf("\n");}// 在链式线性表中删除第i个元素，并用e返回其值void ListDelete(LinkList L,int i,int &e){LinkList p;LinkList q;p=L;int j=0;while(p->next && j<i-1){p=p->next;++j;}if(!(p->next)||j>i-1)printf("没有找到要删除的位置!");else{q=p->next;p->next=q->next;e=q->data;free(q);}}// 用e返回L中第i个数据元素的值void GetList(LinkList L,int i,int &e){LinkList p;p=L->next;int j=0;while(p->next && j<i-1){p=p->next;++j;}if(!(p)||j>i-1)printf("没有找到要查找的位置!");elsee=p->data;}// 对比a与b相等bool compare(int a,int b){if(a==b)return 1;elsereturn 0;}// 在链式线性表L中查找第1个值与e满足compare()d元素的位序void LocateElem(LinkList L,int e){int i=0;LinkList p;p=L;while(p->next && !compare(p->data,e)){p=p->next;i++;}if(NULL==p->next){if(0==compare(p->data,e))printf("没有该元素!\n");elseprintf("第1个与e相等的元素的位序为%d\n",i);}elseif(compare(p->data,e))printf("没有该元素!\n");}LinkList MergeList_L(LinkList La,LinkList Lb){int i,j,k;LinkList pa_1,pb_1,pa_2,pb_2,pc,pd;pa_1=La->next;pc=pa_2=La;pb_1=pb_2=Lb->next;if(pa_1->data > pb_1->data){pc=pa_2=Lb;pa_1=Lb->next;pb_1=pb_2=La->next;}while(pa_1 && pb_1){if(pa_1->data >= pb_1->data){pa_2->next=pb_1;pb_2=pb_1->next;pb_1->next=pa_1;pb_1=pb_2;pa_2=pa_2->next;}else{pa_1=pa_1->next;pa_2=pa_2->next;}}if(pb_1)pa_2->next=pb_1;pd=(LinkList)malloc(sizeof(struct LNode));pd->next=NULL;pa_2=pd;k=total;for(i=0;i<total;i++){pa_1=pc->next;for(j=1;j<k;j++)pa_1=pa_1->next;pb_1=(LinkList)malloc(sizeof(struct LNode));pa_2->next=pb_1;pa_2=pa_2->next;pa_2->data=pa_1->data;k--;}pa_2->next=NULL;return pd;}2.流程图(实验要求1和3)图1 主函数流程图图2创建线性表La流程图图3判断La是否为空表流程图图4 插入元素(La)流程图图5删除元素(La)流程图图6定位元素(La)流程图图7取元素(La)流程图图8输出线性表流程图图9输出线性表流程图流程图(实验要求2和4)图10主函数流程图图11创建线性表La流程图图12判断是否为空表流程图图13插入元素流程图图14删除元素流程图图15定位元素流程图图图16取元素流程图图17创建Lb流程图图18归并两表流程图六、运行结果1. (实验要求1和3)点击运行，首先出现的是菜单界面，选择菜单选项进行操作，如图所示。

计算机软件技术基础实验报告实验一：线性表的排序与查找一．实验内容a)键盘输入一组无序数据,添加到线性表中；b)排序线性表并输出排序结果;c)键盘输入一个数，并插入到排好序的线性表中（要求插入后的表仍为有序表)，输出结果；d)键盘输入一个数,并从线性表中删除相应的数据，输出结果。

二，源程序// Experiment1。

cpp ：定义控制台应用程序的入口点。

//＃include "stdafx.h”#include "iostream”＃include 〈conio。

h〉// 程序实现有各种方法，这里给出一个实例。

// 定义一个线性表const int nMaxSize = 15；// 最大值int nLen = 0; // 表中元素个数int nLinearList[nMaxSize];// 定义操作void LSort（)；void LOut（)；void LInsert(int n）；void LDelete（int n）；int main(int argc，TCHAR＊argv［])｛// 输入数据并放入线性表中printf(”Pleas e input data\n"); // std::cout 〈< "Please input data\n”；int nIn = 0;for (int i = 1; i <= 10；i++)｛scanf(”％d”,＆nIn）；// std:：cin >〉nIn；nLinearList［i] = nIn；nLen++；｝LSort（)；// 排序线性表LOut（)；// 输出结果printf(”Please input a data to i nsert \n”）;scanf(”％d”，&nIn)；LInsert（nIn)；// 输入一个数字，并插入到线性表中LOut（）;printf(”Please input a data to delete \n");scanf("％d”,&nIn）;LDelete（nIn)；// 输入一个数字，并从线性表中删除LOut(）；char chTmp;printf(”Please input a char to finish this program."）；chTmp = getch(）;return 0;｝void LSort(）// 冒泡排序,由大到小｛int j，F,k,M;F=nLen；while(F〉0）{k=F-1;F=0；for（j=1;j<=k;j++）｛if(nLinearList［j］〈nLinearList［j+1］)｛M=nLinearList［j］；nLinearList[j]=nLinearList［j+1]；nLinearList[j+1]=M；F=j；}｝}｝void LOut(){printf（"\n”）;for （int i = 1；i 〈= nLen；i++）{printf( "％d, ", nLinearList[i］);}printf（”\n”）;｝void LInsert(int n）｛int i,j；i=1；while (i<nLen){ if（nLinearList［i］〈=n)｛nLen++；for（j=nLen；j>=i;j—-）nLinearList［j+1］=nLinearList［j］；nLinearList[i］=n；break；}i++；}}void LDelete(int n）{int i,j；for(i=1;i<=nLen；i++){if（nLinearList［i］==n）｛for（j=i；j〈=(nLen—1）；j++)nLinearList［j］=nLinearList[j+1］;nLen—-;break;}｝｝三运行结果实验2：栈与队列的应用一．实验内容a)键盘输入算数表达式，并放入队列当中；b)应用栈的概念设计表达式求值算法；输出表达式求值结果二．源程序// Experiment2。

实验报告课程名称：数据结构实验名称：线性表班级：学生姓名：学号：指导教师评定：签名:题目：有两张非递增有序的线性学生表A，B，采用顺序存储结构，两张表合并用c表存，要求C为非递减有序的，然后删除C表中值相同的多余元素。

一、需求分析⒈本演示程序根据已有的两张表的信息，实现两张表的合并及删除值相同元素的操作，需要用户输入学生的信息。

⒉在演示过程序中，用户输入需要合并的顺序表，即可观看合并结果。

⒊程序执行的命令包括：（1）构造线性表A （2）构造线性表B （3）求两张表的并（4）删除C中值相同的元素二、概要设计⒈为实现上述算法，需要线性表的抽象数据类型：ADT Stack {数据对象：D={a i:|a i∈ElemSet,i=1…n,n≥0}数据关系：R1={<a i-1,a i>|a i-1,a i∈D,i=2,…n≥0}基本操作:init(list *L)操作结果：构造一个空的线性表L。

ListLength(List *L)初始条件：线性表L已经存在操作结果：返回L中数据元素的个数。

GetElem(List L, int i, ElemType *e)初始条件：线性表L已经存在，1≤i≤ListLength(&L)操作结果：用e返回L中第i个数据元素的值。

EqualList(ElemType *e1,ElemType *e2)初始条件：数据元素e1,e2存在操作结果：以e1,e2中的姓名项作为判定e1,e2是否相等的依据。

Less_EquaList(ElemType *e1,ElemType *e2)初始条件：数据元素e1,e2存在操作结果：以e1,e2中的姓名项(为字符串)的≤来判定e1,e2是否有≤的关系。

LocateElem(List *La,ElemType e,int type)初始条件：线性表La已经存在操作结果：判断La中是否有与e相同的元素。

MergeList(List *La,List *Lb,List *Lc)初始条件：非递减线性表La，Lb已经存在操作结果：合并La，Lb得到Lc，Lc仍按非递减有序排列。

实验一线性表的基本操作一、实验目的学习掌握线性表的顺序存储结构、链式存储结构。

设计顺序表的创建、插入、删除等基本操作，设计单链表的建立、插入、删除等基本操作。

二、实验内容1.顺序表的实践（1）顺序表的创建：基于顺序表的动态分配存储结构，创建一个顺序表S，初始状态S=(1，2，3，4，5)。

（2）顺序表的遍历：依次输出顺序表的每个数据元素。

（3）顺序表的插入：在顺序表S=(1，2，3，4，5)的数据元素4和5之间插入一个值为9的数据元素。

（4）顺序表的删除：顺序表S=(1，2，3，4，9，5)中删除指定位置（i=3）的数据元素3。

（5）顺序表的按值查找：查找顺序表S中第1个值等于4的数据元素位序。

（6）顺序表的清空：释放顺序表的存储空间。

2.单链表的实践（1）单链表的创建：创建一个包括头结点和4个元素结点的单链表L=（5，4，2，1）。

（2）单链表的遍历：依次输出顺序表的每个数据元素。

（3）单链表的取值：输出单链表中第i个（i=2）数据元素的值。

（4）单链表的插入：在已建好的单链表的指定位置（i=3）插入一个结点3。

（5）单链表的删除：在一个包括头结点和5个结点的单链表L=（5，4，3，2，1）中，删除指定位置（i=2）的结点，实现的基本操作。

（6）求单链表的表长：输出单链表的所有元素和表长。

（7）单链表的判空：判断单链表是否为空表。

（8）单链表的清空：释放单链表的存储空间。

三、程序源代码1.线性表的基本操作#include <iostream>#include<stdlib.h>using namespace std;#define OK 1#define OVERFLOW -2#define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCEREMENT 10typedef int Status;typedef int Elemtype;typedef Elemtype *Triplet;typedef struct { //定义结构体类型：顺序表Elemtype *elem;int length;int listsize;} Sqlist;Status Initlist( Sqlist &L ) { //int n,i;L.elem = (Elemtype*) malloc (LIST_INIT_SIZE*sizeof(Elemtype));if(!L.elem) {return(OVERFLOW);}cout << "输入元素个数和各元素的值:";cin >> n;for(int i=0; i<n; i++) {cin >> L.elem[i];}L.length = n;L.listsize = LIST_INIT_SIZE;return OK;}Status TraverList(Sqlist L) {for(int i=0; i<L.length; i++) {cout << L.elem[i]<<" ";}cout << endl;}Status ListInsert (Sqlist &L,int i,Elemtype e) { //插入Elemtype *newbase,*p,*q;if(i<1||i>L.length+1) return ERROR;//i不合法if(L.length >= L.listsize) { //需要重新分配存储空间newbase = (Elemtype *) realloc(L.elem,(L.listsize + LISTINCEREMENT)*sizeof (Elemtype));if(!newbase) exit(OVERFLOW);//分配失败L.elem = newbase;L.listsize += LISTINCEREMENT;}q = &(L.elem[i-1]);for(p=&(L.elem[L.length-1]); p>=q; --p)*(p+1)=*p;*q=e;++L.length;return OK;}Status ListDelete(Sqlist &L,int i,Elemtype &e) { //删除Elemtype *p,*q;if((i<1)||(i>L.length)) return ERROR;p=&(L.elem[i-1]);e=*p;q=L.elem+L.length-1;for(++p; p<=q; ++p)*(p-1)=*p;--L.length;return OK;}Status LocateElem(Sqlist L,Elemtype &e) { //查找int i;Elemtype *p;i=1;p=L.elem;while(i<=L.length&&*(p++)!=e) ++i;if(i<=L.length) return i;else return 0;}Status ClearList(Sqlist &L) {free(L.elem);cout << "该表已被清空！";return OK;}int main() {Sqlist L;int i,z;Elemtype e;if(Initlist(L)==OVERFLOW) {cout << endl << "OVERFLOW";return 0;}TraverList(L);while(1) {cout << "-------------------" << endl;cout << "选择要执行的基本操作：" << endl << "1:插入元素" << endl << "2.删除元素" << endl << "3.查找元素" << endl<< "4.退出" << endl;cin >> z;switch(z) {case 1:cout << "输入要插入元素的位置和值：" << endl;cin >> i >> e;if(ListInsert(L,i,e)==OK)TraverList(L);elsecout << "插入的位置不合法。

西安电子科技大学2018年《数据结构与C语言程序设计》考试大纲数据结构与C语言程序设计考研大纲一、考试内容（一）数据结构1.线性表1）线性表的定义2）线性表的顺序存储和基本运算（查找、插入和删除）的实现3）线性表的链式存储和基本运算（查找、插入和删除）的实现4）线性表的应用2.栈、队列和矩阵1）栈和队列的定义2）栈和队列的实现（1）栈的顺序存储和基本操作（入栈、出栈和判栈空、栈满）的实现（2）栈的链式存储和基本操作（入栈、出栈和判栈空）的实现（3）队列的链式存储和基本操作（入队、出队和判队空）的实现（4）循环队列的定义和基本操作（入队、出队和判队空、队满）的实现3）栈和队列的应用4）矩阵的压缩存储（1）特殊矩阵（对称矩阵、三角矩阵、对角矩阵）的压缩存储（2）稀疏矩阵的压缩存储3.树与二叉树1）树的基本概念2）二叉树（1）二叉树的定义及性质（2）二叉树的顺序存储和链式存储（3）二叉树的先序、中序、后序遍历和层序遍历运算（4）线索二叉树的定义3）树和森林（1）树的存储结构（2）树（森林）与二叉树的相互转换（3）树和森林的遍历4）树与二叉树的应用（1）二叉查找树（Binary Search Tree）（2）平衡二叉树（Balanced Binary Tree或Height-Balanced Tree或AVL Tree）（3）哈夫曼（Huffman）树和哈夫曼编码4.图1）图的基本概念2）图的存储（1）数组表示法（邻接矩阵表示法）（2）邻接表表示法3）图的遍历（1）深度优先搜索（DFS）算法（2）广度优先搜索（BFS）算法4）图的应用（1）最小（代价）生成树求解方法（Prim算法和Kruskal算法）（2）最短路径求解方法（Dijkstra算法和Floyd算法）（3）AOV-网和拓扑排序方法（4）AOE-网和关键路径求解方法5.查找1）查找的基本概念2）顺序查找法（1）顺序查找算法（2）平均查找长度计算3）折半查找法（1）折半查找算法（2）折半查找判定树的构造（3）平均查找长度计算4）动态查找表（1）二叉查找树（也称为二叉排序树）的构造及查找、插入和删除运算（2）平衡二叉树的构造及查找运算（3）B-树的特点及查找运算（4）平均查找长度计算5）哈希表（1）哈希表的构造及查找运算（2）平均查找长度计算6）字符串的模式匹配（1）基本的模式匹配算法（2）KMP模式匹配算法（模式串的next函数计算）6.内部排序1）简单排序方法（1）直接插入排序算法（2）冒泡排序算法（3）简单选择排序算法（4）简单排序算法的时间复杂度、空间复杂度及稳定性分析2）快速排序（1）划分过程及分析（2）快速排序算法及其时间复杂度、空间复杂度及稳定性分析3）堆排序（1）堆的定义及初始堆的建立（2）堆排序算法及其时间复杂度、空间复杂度及稳定性分析4）归并排序（1）归并过程及分析（2）二路归并排序算法的时间复杂度、空间复杂度及稳定性分析5）基数排序（1）多关键排序方法（2）链式基数排序方法及特点6）内部排序方法的比较和应用（二）C语言程序设计1.C语言基础（1）数据类型（基本类型和复合类型），常量与变量，运算符与表达式，类型转换；（2）关键字（保留字），用户定义标识符；（3）typedef，sizeof，static，extern，const。