数据结构实验一的源代码

数据结构实验报告实验名称：实验1——单链表的构造学生姓名：XXXXNB班级：XXXX班内序号：学号：XXXX日期：XXXXX1．实验要求根据线性表的抽象数据类型的定义，完成带头结点的单链表的基本功能。

单链表的基本功能：1、构造：使用头插法、尾插法两种方法2、插入：要求建立的链表按照关键字从小到大有序3、删除4、查找5、获取链表长度6、销毁7、其他：可自行定义编写测试main()函数测试线性表的正确性。

2.程序分编程完成单链表的一般性功能如单链表的构造：使用头插法、尾插法两种方法插入：要求建立的链表按照关键字从小到大有序，删除，查找，获取链表长度，销毁用《数据结构》中的相关思想结合C++语言基本知识编写一个单链表结构。

本程序为使用方便，几乎不用特殊的命令，只需按提示输入即可，适合更多的用户使用。

2.1 存储结构单链表的存储结构：2.2 关键算法分析1.头插法自然语言描述：a.在堆中建立新结点b.将a[i]写入到新结点的数据域c.修改新结点的指针域d.修改头结点的指针域,将新结点加入链表中//在构建之初为了链表的美观性构造，进行了排序代码描述：//头插法构造函数template<class T>LinkList<T>::LinkList(T a[], int n){for (int i = n - 1; i >= 1; i--)//冒泡排序，对数组进行从小到大排序{for (int j = 0; j < i; j++){if (a[j]>a[j + 1]){T t = a[j + 1];a[j + 1] = a[j];a[j] = t;}}}front = new Node < T >;//为头指针申请堆空间front->next = NULL;//构造空单链表for (int i = n - 1; i >= 0; i--){Node<T>*s = new Node < T >;//建立新结点s->data = a[i];//将a[i]写入新结点的数据域s->next = front->next;//修改新结点的指针域front->next = s;//修改头结点的指针域，将新结点加入到链表中}}2.尾插法自然语言描述：a.在堆中建立新结点b.将a[i]写入到新结点的数据域c.将新结点加入到链表中d.修改修改尾指针代码描述://尾插法构造函数template<class T>LinkList<T>::LinkList(T a[], int n){front = new Node < T > ;Node<T>*r = front;//命名一个新变量进行转换for (int i = 0; i < n; i++){Node<T>*s = new Node < T > ;s->data = a[i];r->next = s;r = s;}r->next = NULL;}时间复杂度：O(n)3.析构函数自然语言描述：a.新建立一个指针，指向头结点b.移动a中建立的指针c.逐个释放指针代码描述:template<class T>LinkList<T>::~LinkList()//析构函数，销毁链表{Node<T> * p = front;while(p){front = p;p = p->next;delete front;}}4.按位查找函数自然语言描述: a.初始化工作指针p和计数器j，p指向第一个结点，j=1b.循环以下操作，直到p为空或者j等于1b1：p指向下一个结点b2：j加1c.若p为空，说明第i个元素不存在，抛出异常d.否则，说明p指向的元素就是所查找的元素，返回元素地址代码描述:template<class T>Node<T>* LinkList<T>::Get(int i)//按位查找{Node<T> * p = front;int j=0;while(p){if(j<i){p = p->next;j++;}else break;}if(!p) throw"查找位置非法";else return p;}时间复杂度：O(n)5.按值查找函数自然语言描述：a.初始化工作指针p和计数器j，p指向第一个结点，j=1b.循环以下操作，找到这个元素或者p指向最后一个结点b1.判断p指向的结点是不是要查找的值，如果是，返回j;b2.否则p指向下一个结点,并且j的值加一c.如果找到最后一个结点还没有找到要查找的元素，返回查找失败信息代码描述:template<class T>int LinkList<T>::Locate(T x)//按值查找{Node<T> * p = front->next;int j = 1;while(p){if(p->data == x) return j;else{p = p->next;j++;}}return -1;}时间复杂度：O(n)6.插入函数自然语言描述：a.在堆中建立新结点b.将要插入的结点的数据写入到新结点的数据域c.修改新结点的指针域d.修改前一个指针的指针域，使其指向新插入的结点的位置代码描述:template<class T>void LinkList<T>::Insert(int i,T x)//插入函数{Node<T> * p = Get(i-1);if(p){Node<T> * s = new Node<T>;s->data = x;s->next = p->next;p->next = s;}else throw"插入位置非法";}时间复杂度：O(n)7.按位删除函数自然语言描述：a.从第一个结点开始，查找要删除的位数i前一个位置i-1的结点b.设q指向第i个元素c.将q元素从链表中删除d.保存q元素的数据e.释放q元素代码描述:template<class T>T LinkList<T>::Delete(int i)//删除函数{Node<T> *p = Get(i-1);Node<T> *q = p->next;T x=q->data;p->next = q->next;delete q;return x;}8.遍历打印函数自然语言描述: a.判断该链表是否为空链表，如果是，报错b.如果不是空链表，新建立一个temp指针c.将temp指针指向头结点d.打印temp指针的data域e.逐个往后移动temp指针，直到temp指针的指向的指针的next域为空代码描述:template<class T>void LinkList<T>::PrintList()//打印链表{Node<T> * p = front->next;while(p){cout<<p->data<<' ';p = p->next;}cout<<endl;}9.获取链表长度函数自然语言描述：a.判断该链表是否为空链表，如果是，输出长度0b.如果不是空链表，新建立一个temp指针，初始化整形数n为0c.将temp指针指向头结点d.判断temp指针指向的结点的next域是否为空，如果不是，n加一，否则return ne.使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next 域为0，返回n代码描述:template<class T>int LinkList<T>::GetLength()//分析链表长度{Node<T> * p = front;int i=0;while(p){p = p->next;i++;}return i-1;}2.3 其他异常处理采用try catch 函数处理异常如在插入时的异常处理：template<class T>void LinkList<T>::Insert(int i, T x){Node<T>*p = front;if (i != 1) p = Get(i - 1);try{if (p){Node<T>*s = new Node < T > ;s->data = x;s->next = p->next;p->next = s;}else throw i;}catch (int i){cout << "插入到位置 " << i << " 处" << "为错误位置"<<endl;}}3. 程序运行结果主函数流程图：测试截图：初始化链表，菜单创建执行功能：4. 总结.调试时出现了一些问题如：异常抛出的处理，书中并未很好的提及异常处理，通过查阅资料，选择用try catch 函数对解决。

实验报告（2014 / 2015 学年第二学期）课程名称数据结构实验名称线性表的基本运算及多项式的算术运算实验时间2015 年9 月28 日指导单位计算机科学与技术系指导教师黄海平学生姓名陈明阳班级学号Q学院(系) 贝尔英才专业信息科技强化班实验报告~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;T *elements;};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; return false;}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 bounds"<< endl;return false;}if (n == maxLength){cout <<"over flow"<< 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 (i<0 || i>n - 1){cout <<"out of bounds"<< endl;return false;}if (!n){cout <<"over flow"<< 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] << " ";out<< endl;}源.cpp:#include"seqlist.h"const int SIZE = 20;void main(){SeqList<int> LA(SIZE);int i = 0;for (i = 0; i<5; i++) LA.Insert(i - 1, i);LA.Insert(-1, 10);LA.Output(cout);}实现在线性表LA中插入0-4然后在一开始插入10 运行截图如下：多项式实验：定义类如下重构函数如下：源码：#include<iostream>using namespace std;class Term{public:Term(int c, int e);Term(int c, int e, Term* nxt);Term* InsertAfter(int c, int e);private:int coef;int exp;Term* link;friend ostream& operator<<(ostream &, const Term &);friend class Polynominal;};Term::Term(int c, int e) :coef(c), exp(e){link = 0;}Term::Term(int c, int e, Term *nxt) : coef(c), exp(e) {link = nxt;}Term* Term::InsertAfter(int c, int e){link = new Term(c, e, link);return link;}ostream& operator<<(ostream& out, const Term& val){if (0 == val.coef)return out;if (1!= val.coef)out<<val.coef;switch (val.exp){case 0:break;case 1:out<<"X"; break;default:out<<"X^"<<val.exp; break;}return out;}class Polynominal{public:Polynominal();~Polynominal();void AddTerms(istream& in);void Output(ostream& out)const;void PolyAdd(Polynominal& r);void PolyMul(Polynominal& r);private:Term* theList;friend ostream& operator<<(ostream &, const Polynominal &);friend istream& operator>>(istream&, Polynominal &);friend Polynominal& operator+(Polynominal &, Polynominal &);friend Polynominal& operator*(Polynominal &, Polynominal &); };Polynominal::Polynominal(){theList = new Term(0, -1); //头结点theList->link = NULL; //单链表尾结点指针域为空}Polynominal::~Polynominal(){Term* p = theList->link;while (p != NULL){theList->link = p->link;delete p;p = theList->link;}delete theList;}void Polynominal::AddTerms(istream & in){Term* q = theList;int c, e;for (;;){cout <<"Input a term(coef,exp):\n"<< endl;cin >> c >> e;q = q->InsertAfter(c, e);if (0 >= e) break;}}void Polynominal::Output(ostream& out)const{int first = 1;Term *p = theList->link;for (; p != NULL && p->exp >= 0; p = p->link){if (!first && (p->coef>0)) out<<"+";first = 0;out<< *p;}cout << endl;}void Polynominal::PolyAdd(Polynominal& r){Term *q, *q1 = theList, *p; //q1指向表头结点p = r.theList->link; //p指向第一个要处理的结点q = q1->link; //q1是q的前驱，p和q就指向两个当前进行比较的项while (p != NULL && p->exp >= 0)//对r的单循环链表遍历，知道全部结点都处理完{while (p->exp < q->exp) //跳过q->exp大的项{q1 = q;q = q->link;}if (p->exp == q->exp) //当指数相等时，系数相加{q->coef = q->coef + p->coef;if (q->coef == 0) //若相加后系数为0，则删除q{q1->link = q->link;delete(q);q = q1->link; //重置q指针}else{q1 = q; //若相加后系数不为0，则移动q1和qq = q->link;}}else//p>exp>q->exp的情况q1 = q1->InsertAfter(p->coef, p->exp); //以p的系数和指数生成新结点，插入q1后 p = p->link;}}void Polynominal::PolyMul(Polynominal& r){Polynominal result; //定义相乘后的数据Term *n = result.theList; //n指向result的头结点n = n->InsertAfter(0, 0); //在result的头结点后插入新结点，系数指数均为0 Term *p = r.theList->link; //p指向第一个要处理的结点while(p->exp >= 0) //对r的单循环链表遍历{Polynominal tmp; //存储某段相乘后的数据Term *m = tmp.theList; //m指向tmp的头结点Term *q = theList->link; //q指向表头结点的后继结点while(q->exp >= 0) //对当前对象的单循环环链表遍历{m = m->InsertAfter((p->coef)*(q->coef), (p->exp) + (q->exp)); //生成新结点插入n后 q = q->link;}result.PolyAdd(tmp); //将temp加到result上p = p->link;}Term *q = theList->link; //q指向表头结点的后继结点while(q != NULL) //删除原对象的所有数据{theList->link = q->link;delete q;q = theList->link;}q = theList;q = q->InsertAfter(0, 0);PolyAdd(result); //将result加到当前对象上}ostream &operator<<(ostream& out, const Polynominal& x){x.Output(out);return out;}istream &operator>>(istream& in, Polynominal &x){x.AddTerms(in);return in;}Polynominal & operator + (Polynominal &a, Polynominal &b){a.PolyAdd(b);return a;}Polynominal & operator * (Polynominal &a, Polynominal &b){a.PolyMul(b);return a;}int main()实验报告文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.。

数据结构上机实验源代码栈的应用十进制数转换为八进制数，逆序输出所输入的数实验代码：//stack.h，头文件class stack{public:stack();bool empty()const;bool full()const;error_code gettop(elementtype &x)const;error_code push(const elementtype x);error_code pop();private:int count;elementtype data[maxlen];};stack::stack(){count=0;}bool stack::empty()const{return count==0;}bool stack::full()const{return count==maxlen;}error_code stack::gettop(elementtype &x)const{if(empty())return underflow;else{x=data[count-1];return success;}}error_code stack::push(const elementtype x){if(full())return overflow;data[count]=x;count++;return success;}error_code stack::pop(){if(empty())return underflow;count--;return success;}//主程序#include<iostream.h>enum error_code{overflow,underflow,success};typedef int elementtype;const int maxlen=20;#include"stack.h"void read_write() //逆序输出所输入的数{stack s;int i;int n,x;cout<<"please input num int n:";cin>>n;for(i=1;i<=n;i++){cout<<"please input a num:";cin>>x;s.push(x);}while(!s.empty()){s.gettop(x);cout<<x<<" ";s.pop();}cout<<endl;}void Dec_to_Ocx(int n) //十进制转换为八进制{stack s1;int mod,x;while(n!=0){mod=n%8;s1.push(mod);n=n/8;}cout<<"the ocx of the dec is:";while(!s1.empty()){s1.gettop(x);cout<<x;s1.pop();}cout<<endl;}void main(){int n;// read_write();cout<<"please input a dec:";cin>>n;Dec_to_Ocx(n);}队列的应用打印n行杨辉三角实验代码：//queue.hclass queue{public:queue(){count=0;front=rear=0;}bool empty(){return count==0;}bool full(){return count==maxlen-1;}error_code get_front(elementtype &x){if(empty())return underflow;x=data[(front+1)%maxlen];return success;}error_code append(const elementtype x){if(full())return overflow;rear=(rear+1)%maxlen;data[rear]=x;count++;return success;}error_code serve(){if(empty())return underflow;front=(front+1)%maxlen;count--;return success;}private:int count;int front;int rear;int data[maxlen];};//主程序#include<iostream.h>enum error_code{overflow,underflow,success};typedef int elementtype;const int maxlen=20;#include"queue.h"void out_number(int n) //打印前n行的杨辉三角{int s1,s2;int i;int j;int k;queue q;for(i=1;i<=(n-1)*2;i++)cout<<" ";cout<<"1 "<<endl;q.append(1);for(i=2;i<=n;i++){s1=0;for(k=1;k<=(n-i)*2;k++)cout<<" ";for(j=1;j<=i-1;j++){q.get_front(s2);q.serve();cout<<s1+s2<<" ";q.append(s1+s2);s1=s2;}cout<<"1 "<<endl;q.append(1);}}void main(){int n;cout<<"please input n:";cin>>n;out_number(n);}单链表实验实验目的:实验目的（1）理解线性表的链式存储结构。

2011~2012第一学期数据结构实验报告班级：信管一班学号：201051018姓名：史孟晨实验报告题目及要求一、实验题目设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。

1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统），输出实验结果。

（15分）2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学生的学号、姓名和成绩。

3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。

二、实验要求1．修改算法。

将奇偶排序算法升序改为降序。

（15分）2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。

（45分））3．编译、链接以上算法，按要求写出实验报告（25）。

4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。

5．用A4纸打印输出实验报告。

三、实验报告说明实验数据可自定义，每种排序算法数据要求均不重复。

(1) 实验题目：《N门课程学生成绩名次排序算法实现》；(2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性；(3) 实验要求：对算法进行上机编译、链接、运行；(4) 实验环境（Windows XP-sp3,Visual c++)；(5) 实验算法（给出四种排序算法修改后的全部清单）；(6) 实验结果（四种排序算法模拟运行后的实验结果）；(7) 实验体会（文字说明本实验成功或不足之处）。

三、实验源程序（算法）Score.c#include "stdio.h"#include "string.h"#define M 6#define N 3struct student{ char name[10];int number;int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M];void changesort(struct student a[],int n,int j){int flag=1,i;struct student temp;while(flag){ flag=0;for(i=1;i<n-1;i+=2) /*对所有奇数项进行一遍比较*/ if (a[i].score[j]>a[i+1].score[j]){ temp=a[i];a[i]=a[i+1];a[i+1]=temp;flag=1;}for(i=0;i<n-1;i+=2) /*对所有偶数项进行一遍比较*/if (a[i].score[j]>a[i+1].score[j]){ temp=a[i];a[i]=a[i+1];a[i+1]=temp;flag=1;}}}void print_score(struct student a[],int n,int j){ int i,k;printf(“ 奇偶交换成绩 %d 排序表",j+1);printf("\n");printf(" 名次学号姓名分数\n");k=1;for(i=0;k<N&&i<n;i++){ if(i>0&&a[i].score[j]!=a[i-1].score[j])k++;p rintf(" %4d ",k);p rintf("%4d",a[i].number);p rintf(" %s",a[i].name);p rintf(" %6d",a[i].score[j]);p rintf("\n");}}main(){ int i,j,k;for (i=0;i<M;i++) /*输入每个学生信息*/{ printf("请输入第 %d 名学生分数: ",i+1);printf("\n"); printf("姓名: ");s canf("%s",stu[i].name);printf("编号: ");scanf("%4d",&stu[i].number);printf("数据结构: ");scanf("%4d",&stu[i].score[0]);printf("离散数学: ");scanf("%4d",&stu[i].score[1]);printf("大学英语: ");scanf("%4d",&stu[i].score[2]);}for(i=0;i<M;i++) /*计算每个学生总分*/{ stu[i].score[N]=0;for(j=0;j<N;j++)stu[i].score[N]+=stu[i].score[j];}changesort(stu,M,N); /*对总分进行排序*/printf(" 学生总分成绩排序表\n");printf(" 名次学号姓名数据结构离散数学大学英语总分\n"); k=1;for(i=0;i<M;i++){ if(i>0&&stu[i].score[N]!=stu[i-1].score[N])k++;printf("%4d",k);printf(" %4d",stu[i].number);printf(" %s",stu[i].name);for(j=0;j<N+1;j++)printf(" %6d",stu[i].score[j]);printf("\n");}changesort(stu,M,0); /*对数据结构成绩进行排序*/print_score(stu,M,0); /*输出数据结构前 3 名同学成绩*/changesort(stu,M,1); /*对离散数学成绩进行排序*/print_score(stu,M,1); /*输出离散数学前 3 名同学成绩*/changesort(stu,M,2); /*对大学英语成绩进行排序*/print_score(stu,M,2); /*输出大学英语前 3 名同学成绩*/}源代码结果：请输入第1 名学生分数: 姓名: 史孟晨编号: 01数据结构: 87离散数学: 90大学英语: 78请输入第2 名学生分数: 姓名: 袁欣编号: 02数据结构: 78离散数学: 80大学英语: 92请输入第 3 名学生分数: 姓名: 赵宇编号: 03数据结构: 88离散数学: 76大学英语: 95请输入第4 名学生分数: 姓名: 滕芷编号: 04数据结构: 79离散数学: 84大学英语: 88请输入第5 名学生分数: 姓名: 张一析编号: 05数据结构: 78离散数学: 68大学英语: 91请输入第6 名学生分数: 姓名: 白晓彤编号: 06数据结构: 88离散数学: 76大学英语: 90学生总分成绩排序表名次学号姓名数据结构离散数学大学英语总分1 5 张一析78 68 91 2372 2 袁欣78 80 92 2503 4 滕芷79 84 88 2514 6 白晓彤88 76 90 2545 1 史孟晨87 90 78 2556 3 赵宇88 76 95 259 奇偶交换成绩1 排序表名次学号姓名分数1 5 张一析781 2 袁欣782 4 滕芷793 1 史孟晨87奇偶交换成绩2 排序表名次学号姓名分数1 5 张一析682 6 白晓彤762 3 赵宇763 2 袁欣80奇偶交换成绩3 排序表名次学号姓名分数1 1 史孟晨782 4 滕芷883 6 白晓彤90Press any key to continue#include "stdio.h"#include "string.h"#define M 6#define N 3void changesort(struct student a[],int n,int j);void print_score(struct student a[],int n,int j);struct student{char name[10];int number;int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/}stu[M];main(){int i,j,k;for (i=0;i<M;i++) /*输入每个学生信息*/{printf("请输入第%d 名学生分数: ",i+1);printf("\n");printf("姓名: ");scanf("%s",stu[i].name);printf("编号: ");scanf("%4d",&stu[i].number);printf("数据结构: ");scanf("%4d",&stu[i].score[0]);printf("离散数学: ");scanf("%4d",&stu[i].score[1]);printf("大学英语: ");scanf("%4d",&stu[i].score[2]);}for(i=0;i<M;i++) /*计算每个学生总分*/{stu[i].score[N]=0;for(j=0;j<N;j++)stu[i].score[N]+=stu[i].score[j];changesort(stu,M,N); /*对总分进行排序*/printf(" 学生总分成绩排序表\n");printf(" 名次学号姓名数据结构离散数学大学英语总分\n");k=0;for(i=0;i<M+1;i++){if(i>0&&stu[i].score[N]!=stu[i-1].score[N]){k++;printf("%4d",k);printf(" %4d",stu[i-1].number);printf(" %s",stu[i-1].name);for(j=0;j<N+1;j++){printf(" %6d",stu[i-1].score[j]);}}printf("\n");}changesort(stu,M,0); /*对数据结构成绩进行排序*/print_score(stu,M,0); /*输出数据结构前3 名同学成绩*/changesort(stu,M,1); /*对离散数学成绩进行排序*/print_score(stu,M,1); /*输出离散数学前3 名同学成绩*/changesort(stu,M,2); /*对大学英语成绩进行排序*/print_score(stu,M,2); /*输出大学英语前3 名同学成绩*/}void changesort(struct student a[],int n,int j){int flag=1,i;struct student temp;while(flag){flag=0;for(i=1;i<n-1;i+=2) /*对所有奇数项进行一遍比较*/if (a[i].score[j] < a[i+1].score[j]){temp=a[i];a[i]=a[i+1];a[i+1]=temp;flag=1;}for(i=0;i<n-1;i+=2) /*对所有偶数项进行一遍比较*/if (a[i].score[j] < a[i+1].score[j]){temp=a[i];a[i]=a[i+1];a[i+1]=temp;flag=1;}}}void print_score(struct student a[],int n,int j){int i,k;printf(" 奇偶交换成绩%d 排序表",j+1);printf("\n");printf(" 名次学号姓名分数\n");k=1;for(i=0;k<N&&i<n;i++){if(i>0&&a[i].score[j]!=a[i-1].score[j])k++;printf(" %4d ",k);printf("%4d",a[i].number);printf(" %s",a[i].name);printf(" %6d",a[i].score[j]);printf("\n");}}升序改降序：请输入第1 名学生分数:姓名: 史孟晨编号: 01数据结构: 87离散数学: 90大学英语: 78请输入第2 名学生分数:姓名: 袁欣编号: 02数据结构: 78离散数学: 80大学英语: 92请输入第3 名学生分数:姓名: 赵宇编号: 03数据结构: 88离散数学: 76大学英语: 95请输入第4 名学生分数:姓名: 滕芷编号: 04数据结构: 79离散数学: 84大学英语: 88请输入第5 名学生分数:姓名: 张一析编号: 05数据结构: 78离散数学: 68大学英语: 91请输入第6 名学生分数:姓名: 白晓彤编号: 06数据结构: 88离散数学: 76大学英语: 90学生总分成绩排序表名次学号姓名数据结构离散数学大学英语总分1 3 赵宇88 76 95 2592 1 史孟晨87 90 78 2553 6 白晓彤88 76 90 2544 4 滕芷79 84 88 2515 2 袁欣78 80 92 2506 5 张一析78 68 91 237 奇偶交换成绩1 排序表名次学号姓名分数1 3 赵宇881 6 白晓彤882 1 史孟晨873 4 滕芷79奇偶交换成绩2 排序表名次学号姓名分数1 1 史孟晨902 4 滕芷843 2 袁欣80 奇偶交换成绩3 排序表名次学号姓名分数1 3 赵宇952 2 袁欣923 5 张一析91 Press any key to continue#include "stdio.h"#include "string.h"#define M 6#define N 3void changesort(struct student a[],int n,int j);void print_score(struct student a[],int n,int j);struct student{char name[10];int number;int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/}stu[M];main(){int i,j,k;for (i=0;i<M;i++) /*输入每个学生信息*/{printf("请输入第%d 名学生分数: ",i+1);printf("\n");printf("姓名: ");scanf("%s",stu[i].name);printf("编号: ");scanf("%4d",&stu[i].number);printf("数据结构: ");scanf("%4d",&stu[i].score[0]);printf("离散数学: ");scanf("%4d",&stu[i].score[1]);printf("大学英语: ");scanf("%4d",&stu[i].score[2]);}for(i=0;i<M;i++) /*计算每个学生总分*/{stu[i].score[N]=0;for(j=0;j<N;j++)stu[i].score[N]+=stu[i].score[j];changesort(stu,M,N); /*对总分进行排序*/printf(" 学生总分成绩排序表\n");printf(" 名次学号姓名数据结构离散数学大学英语总分\n");k=0;for(i=0;i<M+1;i++){if(i>0&&stu[i].score[N]!=stu[i-1].score[N]){k++;printf("%4d",k);printf(" %4d",stu[i-1].number);printf(" %s",stu[i-1].name);for(j=0;j<N+1;j++){printf(" %6d",stu[i-1].score[j]);}}printf("\n");}changesort(stu,M,0); /*对数据结构成绩进行排序*/print_score(stu,M,0); /*输出数据结构前3 名同学成绩*/changesort(stu,M,1); /*对离散数学成绩进行排序*/print_score(stu,M,1); /*输出离散数学前3 名同学成绩*/changesort(stu,M,2); /*对大学英语成绩进行排序*/print_score(stu,M,2); /*输出大学英语前3 名同学成绩*/}void changesort(struct student a[],int n,int j){int flag=1,i,m,k;struct student temp;while(flag){flag=0;for(i=0;i<n-1;i++) /*选择排序法*/{k=i;for(m=i+1;m<n;m++)if (a[m].score[j]>a[k].score[j]){k=m;temp=a[i];a[i]=a[k];a[k]=temp;flag=1;}}}}void print_score(struct student a[],int n,int j){int i,k;printf(" 选择交换成绩%d 排序表",j+1);printf("\n");printf(" 名次学号姓名分数\n");k=1;for(i=0;k<N&&i<n;i++){if(i>0&&a[i].score[j]!=a[i-1].score[j])k++;printf(" %4d ",k);printf("%4d",a[i].number);printf(" %s",a[i].name);printf(" %6d",a[i].score[j]);printf("\n");}}简单选择：请输入第1 名学生分数:姓名: 史孟晨编号: 01数据结构: 87离散数学: 90大学英语: 78请输入第2 名学生分数:姓名: 袁欣编号: 02数据结构: 78离散数学: 80大学英语: 92请输入第3 名学生分数:姓名: 赵宇编号: 03数据结构: 88离散数学: 76大学英语: 95请输入第4 名学生分数:姓名: 滕芷编号: 04数据结构: 79离散数学: 84大学英语: 88请输入第5 名学生分数:姓名: 张一析编号: 05数据结构: 78离散数学: 68大学英语: 91请输入第6 名学生分数:姓名: 白晓彤编号: 06数据结构: 88离散数学: 76大学英语: 90学生总分成绩排序表名次学号姓名数据结构离散数学大学英语总分1 3 赵宇88 76 95 2592 1 史孟晨87 90 78 2553 6 白晓彤88 76 90 2544 4 滕芷79 84 88 2515 2 袁欣78 80 92 2506 5 张一析78 68 91 237 选择交换成绩1 排序表名次学号姓名分数1 3 赵宇881 6 白晓彤882 1 史孟晨873 4 滕芷79选择交换成绩2 排序表名次学号姓名分数1 1 史孟晨902 4 滕芷843 2 袁欣80 选择交换成绩3 排序表名次学号姓名分数1 3 赵宇952 2 袁欣923 5 张一析91 Press any key to continue#include "stdio.h"#include "string.h"#define M 6#define N 3void changesort(struct student a[],int n,int j);void print_score(struct student a[],int n,int j);struct student{char name[10];int number;int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/}stu[M];main(){int i,j,k;for (i=0;i<M;i++) /*输入每个学生信息*/{printf("请输入第%d 名学生分数: ",i+1);printf("\n");printf("姓名: ");scanf("%s",stu[i].name);printf("编号: ");scanf("%4d",&stu[i].number);printf("数据结构: ");scanf("%4d",&stu[i].score[0]);printf("离散数学: ");scanf("%4d",&stu[i].score[1]);printf("大学英语: ");scanf("%4d",&stu[i].score[2]);}for(i=0;i<M;i++) /*计算每个学生总分*/{stu[i].score[N]=0;for(j=0;j<N;j++)stu[i].score[N]+=stu[i].score[j];changesort(stu,M,N); /*对总分进行排序*/printf(" 学生总分成绩排序表\n");printf(" 名次学号姓名数据结构离散数学大学英语总分\n");k=0;for(i=0;i<M+1;i++){if(i>0&&stu[i].score[N]!=stu[i-1].score[N]){k++;printf("%4d",k);printf(" %4d",stu[i-1].number);printf(" %s",stu[i-1].name);for(j=0;j<N+1;j++){printf(" %6d",stu[i-1].score[j]);}}printf("\n");}changesort(stu,M,0); /*对数据结构成绩进行排序*/print_score(stu,M,0); /*输出数据结构前3 名同学成绩*/changesort(stu,M,1); /*对离散数学成绩进行排序*/print_score(stu,M,1); /*输出离散数学前3 名同学成绩*/changesort(stu,M,2); /*对大学英语成绩进行排序*/print_score(stu,M,2); /*输出大学英语前3 名同学成绩*/}void changesort(struct student a[],int n,int j){{int flag=1,i;struct student temp;while(flag){flag=0;for(i=0;i<n;i++) /*冒泡排序法*/if (a[i].score[j] < a[i+1].score[j]){temp=a[i];a[i]=a[i+1];a[i+1]=temp;flag=1;}}}}void print_score(struct student a[],int n,int j){int i,k;printf(" 冒泡交换成绩%d 排序表",j+1);printf("\n");printf(" 名次学号姓名分数\n");k=1;for(i=0;k<N&&i<n;i++){if(i>0&&a[i].score[j]!=a[i-1].score[j])k++;printf(" %4d ",k);printf("%4d",a[i].number);printf(" %s",a[i].name);printf(" %6d",a[i].score[j]);printf("\n");}}运行结果：请输入第1 名学生分数:姓名: 史孟晨编号: 01数据结构: 87离散数学: 90大学英语: 78请输入第2 名学生分数:姓名: 袁欣编号: 02数据结构: 78离散数学: 80大学英语: 92请输入第3 名学生分数:姓名: 赵宇编号: 03数据结构: 88离散数学: 76大学英语: 95请输入第4 名学生分数:姓名: 滕芷编号: 04数据结构: 79离散数学: 84大学英语: 88请输入第5 名学生分数:姓名: 张一析编号: 05数据结构: 78离散数学: 68大学英语: 91请输入第6 名学生分数:姓名: 白晓彤编号: 06数据结构: 88离散数学: 76大学英语: 90学生总分成绩排序表名次学号姓名数据结构离散数学大学英语总分1 3 赵宇88 76 95 2592 1 史孟晨87 90 78 2553 6 白晓彤88 76 90 2544 4 滕芷79 84 88 2515 2 袁欣78 80 92 2506 5 张一析78 68 91 237 冒泡交换成绩1 排序表名次学号姓名分数1 3 赵宇881 6 白晓彤882 1 史孟晨873 4 滕芷79冒泡交换成绩2 排序表名次学号姓名分数1 1 史孟晨902 4 滕芷843 2 袁欣80冒泡交换成绩3 排序表名次学号姓名分数1 3 赵宇952 2 袁欣923 5 张一析91 Press any key to continueJusertsort.c#include "stdio.h"#include "string.h"#define M 6#define N 3void changesort(struct student a[],int n,int j);void print_score(struct student a[],int n,int j);struct student{char name[10];int number;int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/}stu[M];main(){int i,j,k;for (i=0;i<M;i++) /*输入每个学生信息*/{printf("请输入第%d 名学生分数: ",i+1);printf("\n");printf("姓名: ");scanf("%s",stu[i].name);printf("编号: ");scanf("%4d",&stu[i].number);printf("数据结构: ");scanf("%4d",&stu[i].score[0]);printf("离散数学: ");scanf("%4d",&stu[i].score[1]);printf("大学英语: ");scanf("%4d",&stu[i].score[2]);}for(i=0;i<M;i++) /*计算每个学生总分*/{stu[i].score[N]=0;for(j=0;j<N;j++)stu[i].score[N]+=stu[i].score[j];}changesort(stu,M,N); /*对总分进行排序*/printf(" 学生总分成绩排序表\n");printf(" 名次学号姓名数据结构离散数学大学英语总分\n");k=0;for(i=0;i<M+1;i++){if(i>0&&stu[i].score[N]!=stu[i-1].score[N]){k++;printf("%4d",k);printf(" %4d",stu[i-1].number);printf(" %s",stu[i-1].name);for(j=0;j<N+1;j++){printf(" %6d",stu[i-1].score[j]);}}printf("\n");}changesort(stu,M,0); /*对数据结构成绩进行排序*/print_score(stu,M,0); /*输出数据结构前3 名同学成绩*/changesort(stu,M,1); /*对离散数学成绩进行排序*/print_score(stu,M,1); /*输出离散数学前3 名同学成绩*/changesort(stu,M,2); /*对大学英语成绩进行排序*/print_score(stu,M,2); /*输出大学英语前3 名同学成绩*/}void changesort(struct student a[],int n,int j){int i, m;struct student temp;/*插入排序法*/for(i=1; i<n; i++){temp = a[i];for(m=i; m>0 && temp.score[j] > a[m-1].score[j]; m--){a[m] = a[m-1];}a[m] = temp;}}void print_score(struct student a[],int n,int j){int i,k;printf(" 插入交换成绩%d 排序表",j+1);printf("\n");printf(" 名次学号姓名分数\n");k=1;for(i=0;k<N&&i<n;i++){if(i>0&&a[i].score[j]!=a[i-1].score[j])k++;printf(" %4d ",k);printf("%4d",a[i].number);printf(" %s",a[i].name);printf(" %6d",a[i].score[j]);printf("\n");}}请输入第1 名学生分数:姓名: 史孟晨编号: 01数据结构: 87离散数学: 90大学英语: 78请输入第2 名学生分数:姓名: 袁欣编号: 02数据结构: 78离散数学: 80大学英语: 92请输入第3 名学生分数:姓名: 赵宇编号: 03数据结构: 88离散数学: 76大学英语: 95请输入第4 名学生分数:姓名: 滕芷编号: 04数据结构: 79离散数学: 84大学英语: 88请输入第5 名学生分数:姓名: 张一析编号: 05数据结构: 78离散数学: 68大学英语: 91请输入第6 名学生分数:姓名: 白晓彤编号: 06数据结构: 88离散数学: 76大学英语: 90学生总分成绩排序表名次学号姓名数据结构离散数学大学英语总分1 3 赵宇88 76 95 2592 1 史孟晨87 90 78 2553 6 白晓彤88 76 90 2544 4 滕芷79 84 88 2515 2 袁欣78 80 92 2506 5 张一析78 68 91 237 插入交换成绩1 排序表名次学号姓名分数1 3 赵宇881 6 白晓彤882 1 史孟晨873 4 滕芷79插入交换成绩2 排序表名次学号姓名分数1 1 史孟晨902 4 滕芷843 2 袁欣80插入交换成绩3 排序表名次学号姓名分数1 3 赵宇952 2 袁欣923 5 张一析91Press any key to continue心得体会本学期开设的《数据结构基础》课程已经告一段落，现就学习体会进行学习总结.这是一门纯属于设计的科目，它需用把理论变为上机调试。

算法与数据结构课程设计报告设计题目：专业班级学生学号指导教师2014年第1学期第一部分：需求分析1、系统名称：航空客运订票系统航空客运订票的业务活动包括：查询航线、客票预定和办理退票等。

要求在TC或VC环境下设计一个航空客运订票系统，以使上述业务可以借助计算机来完成。

2、要求：(1)每条航线所涉及的信息有：终点站名、航班号、飞机号、飞行日期(星期几)、乘员定额、余票量、已经订票的客户名单(包括姓名、订票量)以及等候替补的客户名单(包括姓名、所需票量)。

(2)作为模拟系统，全部数据可以只存放在内存中。

(3)通过此系统可以实现如下功能：①录入功能：可以录入航班情况②查询功能：根据客户提供的终点站名进行查询，可以输出以下信息：航班号、飞机号、星期几飞行和余票量等。

也可以根据航班号，查询飞机某个航线的情况。

③订票功能：根据客户提出的要求(姓名、终点站名、订票数量)查询该航班的余票量情况。

如尚有足够的余票，则为客户办理订票手续；若已满员或余票量少于订票数量，则需要重新询问客户要求，如需要，可登记排队候补。

④退票功能：根据客户提供的情况(姓名、日期、航班号)，为客户办理退票手续，然后查询该航班是否有人排队候补，若有人排队，则为排在第一位的客户办理订票手续。

第二部分：系统设计图样一：设计说明1：添加航班：整个航班的信息保存在一个结构体flight中，采用结构体数组，每一个航班信息包含航班号、起飞时间、起飞城市、降落时间、降落城市、余票数量。

航班信息通过lulu（）函数进行添加。

添加的信息保存在航班flight结构体数组中。

2：查询航班：查询板块分为两个部分，按姓名查找和按站名查找。

按姓名查找：通过所输入的姓名和已定客户的姓名相匹配，匹配成功则查找成功。

按站名查找：通过所输入的起始站名和终点站名进行匹配，匹配成功则查找成功。

3：订票功能：根据用户的姓名和航班号进行订票，如果所查找的航班号的余票满足用户需要的票数，则订票成功，该信息保存在Customer中，才用结构体数组，包含已定客户的姓名、客户ID、订的票数、起飞时间、起飞城市、降落时间、降落城市、航班号。

数据结构与算法实验源代码本文档为数据结构与算法实验源代码的范本，旨在帮助读者深入理解和实践数据结构和算法的相关知识。

下文将详细介绍各个章节的内容。

⒈引言- 简要介绍数据结构与算法的重要性和应用场景。

- 说明本文档的结构和目的。

⒉数据结构概述- 介绍数据结构的基本概念和分类。

- 详细介绍各种常见数据结构，如数组、链表、栈、队列、树等。

- 提供每种数据结构的定义、操作和应用示例。

⒊算法基础- 介绍算法的基本思想和特性。

- 详细讲解常见的算法设计方法，如递归、分治、贪心、动态规划等。

- 提供每种算法的原理、示例和分析。

⒋排序算法- 介绍各种排序算法的原理和实现方式。

- 包括冒泡排序、选择排序、插入排序、归并排序、快速排序等。

- 提供每种排序算法的时间复杂度和空间复杂度分析。

⒌查找算法- 介绍常用的查找算法，如顺序查找、二分查找、哈希查找等。

- 提供每种查找算法的原理和实现方式。

- 分析每种查找算法的时间复杂度和空间复杂度。

⒍图算法- 介绍图的基本概念和表示方法。

- 详细讲解图的遍历算法，如深度优先搜索和广度优先搜索。

- 介绍最短路径算法，如Dijkstra算法和Floyd-Warshall算法。

- 提供每种图算法的实现示例和应用场景。

⒎高级数据结构与算法- 介绍高级数据结构，如堆、红黑树、AVL树等。

- 详细讲解高级算法，如动态规划、并查集等。

- 提供每种高级数据结构和算法的原理、实现方式和应用示例。

⒏结语- 对数据结构与算法的重要性进行总结。

- 强调学习和实践的重要性。

本文档涉及附件：⒈源代码示例附件，包含了本文中提到的各种数据结构和算法的实现代码。

法律名词及注释：⒈数据结构：指一组数据的存储结构和相应的操作。

⒉算法：指解决特定问题的一系列有序步骤或规则。

⒊时间复杂度：用来度量算法执行时间随输入规模增长时的增长率。

⒋空间复杂度：用来度量算法执行过程中所需存储空间随输入规模增长时的增长率。

南京工程学院实验报告<班级>_<学号>_<实验X>.RAR文件形式交付指导老师。

一、实验目的1.熟悉上机环境，进一步掌握语言的结构特点。

2.掌握线性表的顺序存储结构的定义及实现。

3.掌握线性表的链式存储结构——单链表的定义及实现。

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

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

二、实验内容1.顺序线性表的建立、插入及删除。

2.链式线性表的建立、插入及删除。

三、实验步骤1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。

2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。

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

要求将用户输入的数据按尾插入法来建立相应单链表。

四、程序主要语句及作用程序1的主要代码(附简要注释)public struct sequenlist{public const int MAXSIZE=1024; /*最大值为1024*/public elemtype[] vec;public int len; /* 顺序表的长度 */public sequenlist( int n){vec=new elemtype[MAXSIZE ];len = n;}};class Program{static void Main(string[] args){sequenlist list1 = new sequenlist(5);for (int i = 0; i < 5; i++){list1.vec[i] = i;}for (int i = 0; i < 5; i++){Console.Write("{0}---", list1.vec[i]) ;}Console.WriteLine("\n");Console.WriteLine("表长：{0}\n",list1.len );Console.ReadKey();}}程序2的主要代码(附简要注释)public void insertlist(int i, int x){if (len >= MAXSIZE)throw new Exception("上溢"); /*长度大于最大值则抛出异常*/if (i < 1 || i > len + 1)throw new Exception("位置");/插入位置小于1或大于len+1则抛出插入位置错误的异常for (int j = len; j >= i; j--)vec[j] = vec[j - 1]; //注意第j个元素存在数组下标为j-1处vec[i - 1] = x;len++;}};class Program{static void Main(string[] args){sequenlist list2 = new sequenlist(7);list2.vec[0] = 21;list2.vec[1] = 23;list2.vec[2] = 14;list2.vec[3] = 5;list2.vec[4] = 56;list2.vec[5] = 17;list2.vec[6] = 31;Console.Write("请输入第i个位置插入元素：");int loc =Convert.ToInt32( Console.ReadLine());Console.Write("请输入第{0}个位置插入的元素：", loc);int ele = Convert.ToInt32(Console.ReadLine());Console.WriteLine("插入前的线性表：");for (int i = 0; i < list2.len ; i++){Console.Write("{0}---", list2.vec[i]);}Console.WriteLine("\n");list2.insertlist(loc, ele);Console.WriteLine("插入后的线性表：");for (int i = 0; i < list2.len ; i++){Console.Write("{0}---", list2.vec[i]);}Console.WriteLine("\n");Console.ReadKey();}}程序3的主要代码(附简要注释)class Node{private int num;public int Num{set { num = value; }/输入值get { return num; }/获得值}private Node next;public Node Next{set { next = value; }get { return next; }}}class Pp{static void Main(string[] args){Node head;Node tempNode, tempNode1;int i;head = new Node();Console.WriteLine("输入六项数据：\n");Console.Write("输入第1项数据:");head.Num = Convert.ToInt32(Console.ReadLine());head.Next = null;tempNode = head;for (i = 1; i < 6; i++){tempNode1 = new Node();Console.Write("输入第{0}项数据:",i+1);tempNode1.Num = Convert.ToInt32(Console.ReadLine());/插入项转换为整形数值 tempNode1.Next = null;tempNode.Next = tempNode1;tempNode = tempNode.Next;}Console.WriteLine("线性表:");tempNode = head;for (i = 0; i < 6; i++){Console.Write("{0}", tempNode.Num);if (i < 5){Console.Write("--");}tempNode = tempNode.Next;}Console.ReadKey();}}五、程序运行结果截图程序1程序2程序3六、收获，体会及问题(写得越详细、越个性化、越真实越好，否则我不知道你做这个实验的心路历程，也就无法充分地判断你是否是独立完成的这个实验、你是否在做这个实验时进行了认真仔细地思考、通过这个实验你是否在实践能力上得到了提高)这次试验刚开始做时完全不知道从哪下手，才刚上了几节课，对于线性表、链式表都不是理解的很透彻，不知道用哪个软件编写程序。

实验一线性表的应用[实验目的]：掌握线性表的逻辑定义、线性表的两种存储结构（顺序和链式）；掌握顺序表和链表的定义及基本操作，运用其解决一些实际问题。

[实验题目]：1、请编写26个字母按特定字母值插入或删除的完整程序，可自行选用顺序存储或链表结构。

答：#include<stdio.h>#include<stdlib.h>typedef struct liuyu{char data;struct liuyu*link;}test;liuyu *p,*q,*r,*head;int L;int m=sizeof(test);void build();void display();int insert_char(char,char);int delet_char(char);void build(){int i;head=(test*)malloc(m);p=head;for(i=1;i<L;i++){p->data=i+'a'-1;p->link=(test*)malloc(m);p=p->link;}p->data=i+'a'-1;p->link=NULL;}void display(){p=head;while(p->link!=NULL){printf("%c",p->data);p=p->link;}printf("%c\n",p->data);}int insert_char(char X,char Y){p=head;r=(test*)malloc(m);r->data=X;if(head->data==Y){head=r;r->link=p;}else{while((p->data!=Y)&&(p->link!=NULL)){q=p;p=p->link;}if(p->data==Y){q->link=r;r->link=p;}else{p->link=r;r->link=NULL;}}L++;return(0);}int delet_char(char X){p=head;if(head->data==X){head=head->link;free(p);} else {while((p->data!=X)&&(p->link!=NULL)) {q=p;p=p->link;}if(p->data==X){q->link=p->link;free(p);}else return(-1);}L--;return(0);}void main(void){L=26;build();display();printf("insert return value=%d\n",insert_char('L','W')); display();printf("delete return value=%d\n",delet_char('z')); display();}程序运行结果为：2、创建一个链表。

- 1 -实验一：实现单链表各种基本运算的算法一、 实验目的1、 掌握单链表存储结构的类型定义；2、 实现单链表各种基本运算的算法。

二、 实验环境1、 Windows 操作系统；2、 Visual C++ 6.0三、 实验内容实现单链表各种基本运算的算法。

四、 概要设计1.存储结构的类型定义：Typedef struct LNode{ElemType data;Struct LNode *next;}LinkList;2.单链表示意图：3.项目组成图:4.algo2_2.cpp 的程序文件包含的函数原型及功能:InitList(LinkList *&L) 初始化单链表LDestroyList(LinkList *&L) 释放单链表LListEmpty(LinkList *L)判断单链表L 是否为空表ListLength(LinkList *L)返回单链表L 的元素个数DispList(LinkList *L)输出单链表LGetElem(LinkList *L,int i,ElemType &e)获取单链表L 的第i 个元素LocateElem(LinkList *L,ElemType e)在单链表L 中查找元素eListInsert(LinkList *&L,int i,ElemType e)在单链表L 中的第i 个位置上插入元素e…… head a 1 a 2 a 3 a n ∧ListDelete(LinkList *&L,int i,ElemType &e)在单链表L中删除第i个元素5.exp2_2.cpp程序文件简介:InitList(LinkList *&L) 初始化单链表LDestroyList(LinkList *&L) 释放单链表LListEmpty(LinkList *L) 判断单链表L是否为空表ListLength(LinkList *L) 返回单链表L的元素个数DispList(LinkList *L) 输出单链表LGetElem(LinkList *L,int i,ElemType &e) 获取单链表L的第i个元素LocateElem(LinkList *L,ElemType e) 在单链表L中查找元素eListInsert(LinkList *&L,int i,ElemType e) 在单链表L中的第i个位置上插入元素e ListDelete(LinkList *&L,int i,ElemType &e) 在单链表L中删除第i个元素6.proj2-2的项目的模块结构:在文件algo2-2中，(1)定义单链表结构类型；(2)初始化单链表(3)定义释放单链表的函数(4)定义判断单链表是否为空的函数(5)定义返回单链表元素个数的函数(6)定义输出单链表的函数(7)定义获取第i个元素的函数(8)定义查找元素的函数(9)定义插入元素的函数(10)定义删除元素的函数在文件exp2-2中分别调用algo2-2中所定义的函数7.函数调用关系图:五、详细设计源代码清单见附录。

一、实验目的二、实验内容和要求三、源代码1)顺序表的代码2)单链表的代码四、测试结果1)顺序表的测试结果2)单链表的测试结果五、心得体会实验一线性表的基本操作及其应用一、实验目的1、帮助读者复习C++语言程序设计中的知识。

2、熟悉线性表的逻辑结构。

3、熟悉线性表的基本运算在两种存储结构上的实现。

4、掌握顺序表的存储结构形式及其描述和基本运算的实现。

5、熟练掌握动态链表结构及有关算法的设计二、实验内容题目一：顺序表的基本操作[问题描述]实现顺序表的建立、求长度，取元素、修改元素、插入、删除等顺序表的基本操作。

[基本要求]（1）依次从键盘读入数据，建立带头结点的顺序表；（2）输出顺序表中的数据元素（3）求顺序表的长度；（4）根据指定条件能够取元素和修改元素；（5）实现在指定位置插入和删除元素的功能。

（6）根据算法，将两个有序的顺序表合并成一个有序顺序表。

[测试数据] 由学生任意指定。

题目二：单链表的基本操作[问题描述]实现带头结点的单链表的建立、求长度，取元素、修改元素、插入、删除等单链表的基本操作。

[基本要求]（1）依次从键盘读入数据，建立带头结点的单链表；（2）输出单链表中的数据元素（3）求单链表的长度；（4）根据指定条件能够取元素和修改元素；（5）实现在指定位置插入和删除元素的功能。

（6）根据算法，将两个有序的单链表合并成一个有序单链表。

[测试数据]由学生任意指定。

三、源代码(一)顺序表的基本操作#include<iostream>using namespace std;#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef int ElemType;#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct { //结构体ElemType *elem;int length;int listsize;}SqList;SqList Lx;Status InitList_Sq(SqList &L) //分配空间{ L.elem=new ElemType[LIST_INIT_SIZE];if(!L.elem)exit(OVERFLOW);L.length =0;L.listsize=LIST_INIT_SIZE;return OK;}Status ListInsert(SqList &L,int i,ElemType e) //插入新元素{ int *q,*p;ElemType *newbase;if(i<1 || i>L.length+1) return ERROR;if(L.length>=L.listsize){ newbase=new ElemType[L.listsize+LISTINCREMENT];if(!newbase) exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;}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 Listlength(SqList L) //长度{ int *p=L.elem; //判断线形表是否存在while(p){ return (L.length); }}Status GetElem(SqList L, int i,ElemType &e) //取元素{ if(i<1 || i>L.length)return ERROR;else{ e=L.elem[i-1];return e;}}void MergeList(SqList La,SqList Lb,SqList &Lc) //合并{ ElemType ai,bj;InitList_Sq(Lc);int i=1,j=1,k=0;int La_len,Lb_len;La_len=Listlength(La);Lb_len=Listlength(Lb);while((i<=La_len)&&(j<=Lb_len)){ GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai<=bj){ ListInsert(Lc,++k,ai);++i; }else{ ListInsert(Lc,++k,bj);++j; }}while(i<=La_len){ GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len){ GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}void show(SqList L,int i) //显示{ int j;ElemType k;cout<<"顺序表显示如下:"<<endl;for(j=0;j<i-1;j++){ k=L.elem[j];cout<<k<<"->"; }if(j==i-1 && i>0){ k=L.elem[j]; cout<<k; }cout<<endl;}void create(SqList &L,int n) //输入元素{ int e;for(int i=0;i<n;i++)L.elem[i]=e;L.length=i+1; }}Status ListDelete_Sq(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 Listxiugei(SqList &L,int i,ElemType &e) //修改{ if(i<1 || i>L.length)return ERROR;else{ L.elem[i-1]=e;return OK; }}void shuru(SqList &L1) //顺序表的创建{ int a;InitList_Sq(L1);cout<<"请输入顺序表的长度：";cin>>a;cout<<"请输入顺序表的元素(共"<<a<<"个)"<<endl;create(L1,a);show(L1,a);}void chaxun(SqList &L1) //取第i个位置的元素{ int j;ElemType e1;cout<<"请选择所要取出元素的位置:";while(j<0||j>Listlength(L1)){ cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要取出元素的位置:";cin>>j; }GetElem(L1,j,e1);cout<<"取出的元素为:"<<e1<<endl; }void xiugai(SqList &L1) //修改第i个位置的元素{ int a;int j; ElemType e1;a=L1.length;cout<<"请选择所要修改元素的位置:";cin>>j;while(j<0||j>Listlength(L1)){ cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要修改元素的位置:";cin>>j; }cout<<"要修改成的元素:";cin>>e1;Listxiugei(L1,j,e1);cout<<"修改后的顺序表数据:"<<endl;show(L1,a);}void shanchu(SqList &L1) //删除顺序表里的元素{ int a;int j; ElemType e1;a=L1.length;cout<<"请选择所要删除元素的位置:";cin>>j;while(j<0||j>Listlength(L1)){ cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要删除元素的位置:";cin>>j; }ListDelete_Sq(L1,j,e1);cout<<"修改后的顺序表数据:"<<endl;show(L1,a-1);}void charu(SqList &L1) //插入元素到顺序表里{ int a; int j; ElemType e1;a=L1.length;cout<<"请选择所要插入元素的位置:";cin>>j;while(j<0||j>Listlength(L1)){ cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要插入元素的位置:";cin>>j; }cout<<"要插入的元素:";cin>>e1;ListInsert(L1,j,e1);cout<<"修改后的顺序表数据:"<<endl;show(L1,a+1);}void hebing(SqList &L3) //合并两个顺序表{ SqList L1,L2;int a,b;InitList_Sq(L1); InitList_Sq(L2);cout<<"请输入第一个有序表的长度："; cin>>a;cout<<"请输入第一个有序表的元素(共"<<a<<"个)"<<endl;create(L1,a);show(L1,a);cout<<"请输入第二个有序表的长度："; cin>>b;cout<<"请输入第二个有序表的元素(共"<<b<<"个)"<<endl;create(L2,b);show(L2,b);MergeList(L1,L2,L3);cout<<"合并后的有序表如下："; show(L3,a+b);}void main() //主菜单{ int choice;for(;;){ cout<<" 顺序表的基本操作"<<endl;cout<<" 1.顺序表的创建"<<endl;cout<<" 2.顺序表的显示"<<endl;cout<<" 3.顺序表的长度"<<endl;cout<<" 4.取第i个位置的元素"<<endl;cout<<" 5.修改第i个位置的元素"<<endl;cout<<" 6.插入元素到顺序表里"<<endl;cout<<" 7.删除顺序表里的元素"<<endl;cout<<" 8.合并两个顺序表"<<endl;cout<<" 9.退出系统"<<endl;cout<<"请选择：";cin>>choice;switch(choice){ case 1: shuru(Lx);break;case 2: show(Lx,Lx.length);break;case 3: cout<<"顺序表的长度:"<<Listlength(Lx)<<endl;break; case 4: chaxun(Lx);break;case 5: xiugai(Lx);break;case 6: charu(Lx);break;case 7: shanchu(Lx);break;case 8: hebing(Lx);break;case 9: cout<<"退出系统!"<<endl;exit(0);break;default : cout<<"输入有误，请重新选择"<<endl;break; }}}(二)单链表的基本操作#include<iostream>using namespace std;#define true 1#define false 0#define ok 1#define error 0#define overflow -2typedef int Status;typedef int ElemType;typedef struct LNode //存储结构{ ElemType data;struct LNode *next;}LNode,*LinkList;void CreateList(LinkList &L,int n) //尾插法创建单链表{ LinkList p;L=new LNode;L->next=NULL; //建立一个带头结点的单链表LinkList q=L; //使q指向表尾for(int i=1;i<=n;i++){ p=new LNode;cin>>p->data;p->next=NULL;q->next=p;q=p; }}Status GetElem(LinkList L,int i,ElemType &e)//取第i个元素{ LinkList p=L->next;int j=1;while(p&&j<i){ p=p->next;++j; }if(!p||j>i) return error; //第i个元素不存在 e=p->data;return ok;}Status LinkInsert(LinkList &L,int i,ElemType e) //插入{ LinkList p=L;int j=0;while(p&&j<i-1){ p=p->next;++j; } //寻找第i-1个结点 if(!p||j>i-1)return error; //i小于1或者大于表长加1 LinkList s=new LNode; //生成新结点s->data=e;s->next=p->next; //插入L中p->next=s;return ok;}Status ListDelete(LinkList &L,int i,ElemType &e) // 删除{ LinkList p=L;LinkList q;int j=0;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; //删除并释放结点e=q->data;delete(q);return ok;}void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc) { //合并两个顺序链表LinkList pa,pc,pb;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){ if(pa->data<=pb->data){ pc->next=pa;pc=pa;pa=pa->next; }else{ pc->next=pb;pc=pb;pb=pb->next; }}pc->next=pa?pa:pb;delete(Lb);}void show(LinkList L) //显示{ LinkList p;p=L->next;while(p){ cout<<p->data<<"-->";p=p->next; }cout<<endl;}int Length(LinkList L,int i) //表长{ i=0;LinkList p=L->next;while(p){ ++i;p=p->next; }return i;}void xiugai(LinkList L) //修改{ int i,j=1;ElemType k;ElemType e,m;LinkList p=L->next;cout<<"请输入要修改的元素位置(0<i<length):";cin>>i;GetElem(L,i,e);cout<<"该位置的元素:"<<e<<endl;cout<<"修改后的元素值:";cin>>k;while(p&&j<i){ p=p->next;++j; }m=p->data;p->data=k;cout<<"修改后的单链表显示如下:"<<endl;show(L);}void hebing() //合并两个单链表{ int a,b;LinkList La,Lb,Lc;cout<<"请输入第一个有序链表的长度:"<<endl;cin>>a;cout<<"请输入第一个有序链表的元素共（"<<a<<"个）："<<endl;CreateList(La,a);show(La);cout<<"请输入第二个有序链表的长度:"<<endl;cin>>b;cout<<"请输入第二个有序链表的元素共（"<<b<<"个）："<<endl;CreateList(Lb,b);show (Lb);MergeList(La,Lb,Lc);cout<<"合并后的有序链表如下："<<endl;show(Lc);}void main() //主函数{ int select;int x;ElemType y;LinkList list;for(;;){ cout<<" 单链表的基本操作"<<endl;cout<<" 1.单链表的创建"<<endl;cout<<" 2.单链表的显示"<<endl;cout<<" 3.单链表的长度"<<endl;cout<<" 4.取第i个位置的元素"<<endl;cout<<" 5.修改第i个位置的元素"<<endl;cout<<" 6.插入元素到单链表里"<<endl;cout<<" 7.删除单链表里的元素"<<endl;cout<<" 8.合并两个单链表"<<endl;cout<<" 9.退出系统"<<endl;cout<<"请选择:";cin>>select;switch(select){ case 1:cout<<"请输入单链表的长度:"<<endl;cin>>x;cout<<"请输入"<<x<<"个元素"<<endl;CreateList(list,x);break;case 2: cout<<"单链表显示如下:"<<endl;show(list);break;case 3: int s;cout<<"单链表的长度为:"<<Length(list,s)<<endl;break;case 4: cout<<"请选择所要取出元素的位置:";while(x<0||x>Length(list,s)){ cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要取出元素的位置:";cin>>x; }GetElem(list,x,y);cout<<"该位置的元素为:"<<y<<endl;break;case 5: xiugai(list); break;case 6: cout<<"请选择要插入的位置:"; cin>>x;while(x<0||x>Length(list,s)){ cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要插入元素的位置:";cin>>x; }cout<<"要插入的元素值:";cin>>y;LinkInsert( list,x,y);cout<<"插入后单链表显示如下:"<<endl;show(list);break;case 7: cout<<"请选择要删除的位置:"; cin>>x;while(x<0||x>Length(list,s)){ cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要删除元素的位置:";cin>>x; }ListDelete(list,x,y);cout<<"要删除的元素值:"<<y<<endl;cout<<"删除后的单链表显示如下:"<<endl;show(list);break;case 8: hebing();break;case 9: exit(0);default : cout<<"输入有误，请重新输入"<<endl;break;}}}四、测试结果1)顺序表的测试结果2)单链表的测试结果五、心得体会当听到老师说写数据结构实验报告时，我有点惊讶，才学了不到一个月，就要写实验报告。

/*顺序表的操作#include<iostream>#include<stdlib.h>using namespace std;Release 13.12 rev 9501 (2013/12/25 19:25:45) gcc 4.7.1 Windows/unicode - 32 bit #define MAX_SIZE 100typedef struct{int *emel;int lenth;}Sq;void init(Sq &l);void create(Sq &l);void trval(Sq &l);void find_value(Sq &l);void find_position(Sq &l);void insert(Sq &l);void dele(Sq &l);int main(){Sq l;init(l);create(l);trval(l);find_value(l);find_position(l);insert(l);trval(l);dele(l);trval(l);return 0;}void init(Sq &l){l.emel =new int[MAX_SIZE];if(l.emel ==NULL){cout<<"\t申请空间失败！"<<endl;exit(1);}l.lenth=0;cout<<"\t成功申请空间！该顺序表的长度目前为:"<<l.lenth<<endl; }void create(Sq &l){cout<<"\t请输入你想输入元素的个数：";int x;cin>>x;if((x<1)&&(x>MAX_SIZE)){cout<<"\t你说输入的数不在范围里"<<endl;return;}int i;for(i=0;i<x;i++){cin>>l.emel[i];}l.lenth=x;cout<<"\t成功赋值！"<<endl;}void trval(Sq &l){int i;cout<<"l(";for(i=0;i<l.lenth;i++){cout<<l.emel[i]<<" ";}cout<<")"<<" 该顺序表现在的长度为："<<l.lenth<<endl;}void find_value(Sq &l){int x,t=0;cout<<"\t请输入你要查找的值：";cin>>x;int i;for(i=0;i<l.lenth;i++){if(l.emel[i]==x){t=1;cout<<"\t成功找到该元素，它是顺序表的第"<<i+1<<"个元素！"<<endl;}}if(t==0){cout<<"\t无该元素！"<<endl;}}void find_position(Sq &l){int x;cout<<"\t请输入你要查找的位置：";cin>>x;int i;if((x<1)||(x>l.lenth)){cout<<"\t输入的值不在范围内！"<<endl;return;}for(i=1;i<=l.lenth;i++){if(i==x){cout<<"\t成功找到该元素，该值是"<<l.emel[i-1]<<endl;}}}void insert(Sq &l){int i,x,y;cout<<"\t请输入你要插入的位置";cin>>x;cout<<"\t请输入你要插入的值";cin>>y;if((x<1)||(x>l.lenth)){cout<<"\t输入的值不在范围内！"<<endl;return;}if(x==l.lenth){l.emel[l.lenth]=y;l.lenth=l.lenth+1;return;}for(i=l.lenth;i>=x;i--){l.emel[i]=l.emel[i-1];}l.emel[x-1]=y;l.lenth=l.lenth+1;}void dele(Sq &l){int i,x;cout<<"\t请输入你要删除位置：";cin>>x;if((x<1)||(x>l.lenth)){cout<<"\t输入的值不在范围内！"<<endl;return;}for(i=x-1;i<=l.lenth;i++){l.emel[i]=l.emel[i+1];}l.lenth=l.lenth-1;}成功申请空间！该顺序表的长度目前为:0请输入你想输入元素的个数：3852成功赋值！l(8 5 2 ) 该顺序表现在的长度为：3请输入你要查找的值：5成功找到该元素，它是顺序表的第2个元素！请输入你要查找的位置：3成功找到该元素，该值是2请输入你要插入的位置3请输入你要插入的值10l(8 5 2 10 ) 该顺序表现在的长度为：4请输入你要删除位置：3l(8 5 10 ) 该顺序表现在的长度为：3--------------------------------Process exited with return value 0Press any key to continue . . .*//*#include<stdio.h>#include<stdlib.h>typedef struct Link{int num;struct Link *next;}L;L* creat(L* head){head=(L *)malloc(sizeof(L));if(head==NULL){printf("头节点申请失败！\n");exit(-1);}head->next=NULL;return head;}void insert(L* head){int x,i;printf("请输入你想输入数据的个数：");scanf("%d",&x);L *p,*q;p=head;for(i=0;i<x;i++){q=(L *)malloc(sizeof(L));if(q==NULL){printf("新点申请失败！\n");exit(-1);}printf("请输入值：");scanf("%d",&q->num);q->next=NULL;p->next=q;p=q;}}void print(L* head){L *p;p=head->next;while(p!=NULL){printf("值为：%d\n",p->num);p=p->next;}}int main(){L *head;head=creat(head);printf("成功创建头节点！！！\n");insert(head);printf("成功输入数据！！！\n");print(head);return 0;}*//*线性表的操作#include<stdio.h>#include<stdlib.h>typedef struct Link{int num;struct Link *next;}L;L* creat(L* head){head=(L *)malloc(sizeof(L));if(head==NULL){printf("头节点申请失败！\n");exit(-1);}head->next=NULL;return head;}void init(L* head){int x,i;printf("请输入你想输入数据的个数：");scanf("%d",&x);L *p,*q;p=head;for(i=0;i<x;i++){q=(L *)malloc(sizeof(L));if(q==NULL){printf("新点申请失败！\n");exit(-1);}printf("请输入值：");scanf("%d",&q->num);q->next=p->next;p->next=q;}}int print(L* head){L *p;int lenth=0;p=head->next;printf("\t\tL(");while(p!=NULL){lenth++;printf("%d ",p->num);p=p->next;}printf(")\n");return lenth;}int insert(L *head,int lenth){printf("\t\t请输入你要插入的元素的位置:");int in;scanf("%d",&in);if(in<1 || in>lenth){printf("\t\t输入值不在范围内！");return -1;}L *p,*q;p=head->next;q=(L *)malloc(sizeof(L));if(q==NULL){printf("新点申请失败！\n");return -1;}printf("\t\t请为新节点输入值：");scanf("%d",&q->num);int i=0;while(p!=NULL){i++;if(i==in-1){q->next=p->next;p->next=q;}p=p->next;}lenth++;return lenth;}int dele(L *head,int lenth){printf("\t\t请输入你要删除的元素的位置:");int out;scanf("%d",&out);if(out<1 || out>lenth){printf("\t\t输入值不在范围内！");return -1;}L *p,*q;p=head->next;q=head;int i=0;while(p!=NULL){i++;if(i==out){q->next=p->next;}q=p;p=p->next;}lenth--;return lenth;}void find(L *head,int lenth){printf("\t\t请输入你要查找的元素的位置:");int finder;scanf("%d",&finder);if(finder<1 || finder>lenth){printf("\t\t输入值不在范围内！");return ;}L *p;p=head->next;int i=0;while(p!=NULL){i++;if(i==finder){printf("\t\t你要找的该位置所对应的值为：%d\n",p->num);}p=p->next;}}int main(){L *head;head=creat(head);printf("成功创建头节点！！！\n");init(head);printf("成功输入数据！！！\n");int len;len=print(head);printf("\t\t该线性表的长度为:%d\n",len);len=insert(head,len);len=print(head);printf("\t\t插入后线性表的长度为:%d\n",len);len=dele(head,len);len=print(head);printf("\t\t删除后该线性表的长度为:%d\n",len);find(head,len);return 0;}*//*顺序表的合并#include<iostream>using namespace std;struct LA{int *pa;int lenth;};struct LB{int *pb;int lenth;};struct LC{int *pc;int lenth;};void mergelist(LA la,LB lb,LC &lc);int main(){int x,y;LA la;LB lb;cout<<"\t\t请给线性表LA和LB指定长度：";cin>>x>>y;la.pa =new int(sizeof(int)*x);lb.pb =new int(sizeof(int)*y);int i;for(i=0;i<x;i++){cout<<"请输入表LA的值:";cin>>la.pa[i];}cout<<endl;la.lenth=x;for(i=0;i<y;i++){cout<<"请输入表LB的值:";cin>>lb.pb[i];}lb.lenth=y;cout<<"LA(";for(i=0;i<x;i++){cout<<la.pa[i]<<" ";}cout<<")"<<endl;cout<<"LB(";for(i=0;i<y;i++){cout<<lb.pb[i]<<" ";}cout<<")"<<endl;LC lc;mergelist(la,lb,lc);return 0;}void mergelist(LA la,LB lb,LC &lc){lc.lenth=la.lenth+lb.lenth;lc.pc=new int(sizeof(int)*lc.lenth);int *pa=la.pa,*pb=lb.pb,*pc=lc.pc;int *pa_last=la.pa+la.lenth-1;int *pb_last=lb.pb+lb.lenth-1;while(pa<=pa_last && pb<=pb_last){if(*pa <= *pb){*pc++=*pa++;}else{*pc++=*pb++;}}while(pa<=pa_last){*pc++=*pa++;}while(pb<=pb_last){*pc++=*pb++;}cout<<"LC(";int i=0;for(i=0;i<lc.lenth;i++){cout<<lc.pc[i]<<" ";}cout<<")"<<endl;}*///栈/*#include<iostream>using namespace std;#include<stdlib.h>#define MAXSIZE 100typedef struct{int *base;int *top;int stacksize;}Sqstack;int Initstack(Sqstack &s);void Push(Sqstack &s,int e);void StackTraverse(Sqstack &s);void Gettop(Sqstack &s);void Pop(Sqstack &s);int main(){Sqstack s;Initstack(s);cout<<"\t\t初始化栈成功！"<<endl;Push(s,2);cout<<"\t\t2入栈成功！"<<endl;Push(s,4);cout<<"\t\t4入栈成功！"<<endl;Push(s,6);cout<<"\t\t6入栈成功！"<<endl;Push(s,8);cout<<"\t\t8入栈成功！"<<endl;cout<<"\n由栈底至栈顶的元素为：";StackTraverse(s);Gettop(s);Pop(s);Gettop(s);return 0;}int Initstack(Sqstack &s){s.base=new int[MAXSIZE];if(s.base==NULL){exit(1);}s.top=s.base;s.stacksize=MAXSIZE;}void Push(Sqstack &s,int e){if(s.top-s.base==s.stacksize){exit(1);}*s.top++=e;}void StackTraverse(Sqstack &s){int *p=s.base,i=0;while(p<s.top){i++;cout<<*p++<<" ";}cout<<"\t\t栈的长度是"<<i<<endl;}void Gettop(Sqstack &s){if(s.base==s.top){exit(1);}cout<<"栈顶元素是："<<*(s.top-1)<<endl; }void Pop(Sqstack &s){if(s.top==s.base){exit(1);}cout<<"出栈的第一个元素是:";cout<<*--s.top<<" "<<endl;}*///队列例题：/*#include<iostream>#include<stdlib.h>using namespace std;#define MAXQSIZE 100typedef struct{int *base;int front;int rear;}SqQueue;int InitQueue(SqQueue &q);int EnQueue(SqQueue &q,int x);int DeQueue(SqQueue &q);int main(){SqQueue q;InitQueue(q);EnQueue(q,1);EnQueue(q,3);EnQueue(q,5);EnQueue(q,7);DeQueue(q);DeQueue(q);DeQueue(q);DeQueue(q);return 0;}int InitQueue(SqQueue &q){q.base=new int[MAXQSIZE];if(q.base==NULL){exit(1);}q.front=0;q.rear=0;return 0;}int EnQueue(SqQueue &q,int x){if((q.rear+1)%MAXQSIZE==q.front){exit(0);}q.base[q.rear]=x;q.rear=(q.rear+1)%MAXQSIZE;return 0;}int DeQueue(SqQueue &q){if(q.front==q.rear){exit(0);}int x=q.base[q.front];q.front=(q.front+1)%MAXQSIZE;cout<<x<<endl;}*//*#include<iostream>#include<stdlib.h>using namespace std;typedef struct Qnode{int date;struct Qnode *next;}Qnode,*Queueptr;typedef struct{Queueptr front; //队头指针Queueptr rear; //队尾指针}LinkQueue;int InitQueue(LinkQueue &Q);void EnQueue(LinkQueue &Q,int e);void TrvalQueue(LinkQueue Q);void DeQueue(LinkQueue &Q);int main(){LinkQueue Q;InitQueue(Q);EnQueue(Q,1);cout<<"\t元素1入队成功！"<<endl;EnQueue(Q,3);cout<<"\t元素3入队成功！"<<endl;EnQueue(Q,5);cout<<"\t元素5入队成功！"<<endl;EnQueue(Q,7);cout<<"\t元素7入队成功！"<<endl;cout<<"\t队列的元素分别是："<<endl;TrvalQueue(Q);cout<<"\t第一个出队的元素是："<<endl;DeQueue(Q);cout<<"\n\t第一个元素出队完成之后队列中从队头至队尾的元素为：";TrvalQueue(Q);return 0;}int InitQueue(LinkQueue &Q){Q.rear=new Qnode;Q.front=Q.rear;if(Q.front==NULL){exit(0);}Q.front->next=NULL;return 0;}void EnQueue(LinkQueue &Q,int e){Qnode *p=new Qnode;if(!p){exit(1);}p->date=e;p->next=NULL;Q.rear->next=p; //连接Q.rear=p; //修改队尾指针}void TrvalQueue(LinkQueue Q){Qnode *p=Q.front->next;//队头元素while(Q.front!=Q.rear){cout <<p->date<<" ";Q.front=p;p=p->next;}cout<<endl;}void DeQueue(LinkQueue &Q){if(Q.front==Q.rear){return;}Qnode *p=Q.front->next;cout<<"\t"<<p->date<<endl;Q.front->next=p->next;if(Q.rear==p){Q.rear=Q.front;delete p;}}*//*//表达式求值#include<iostream>#include<stdlib.h>#include<stdio.h>using namespace std;#define MAXSIZE 100typedef struct{char *base;char *top;char num;}OPND; //数据栈typedef struct{char *base;char *top;char c;}OPTR; //符号栈int Initstack(OPND &op_n,OPTR &op_t);void Pushstack(OPND &op_n,char ch);void Pushstack(OPTR &op_t,char ch);char Popstack(OPND &op_n,char ch);char Popstack(OPTR &op_t,char ch);char Gettop(OPTR op_t);char Gettop(OPND op_n);int In(char ch);char Precede(char x,char y);char operate(char z,char x,char y);int main(){OPND op_n;OPTR op_t;Initstack(op_n,op_t);Pushstack(op_t,'#');char ch;char p;cin>>ch;while(ch!='#' || Gettop(op_t)!='#'){if(!In(ch)){Pushstack(op_n,ch);cin>>ch;}else{switch( Precede(Gettop(op_t),ch) ){case '<':Pushstack(op_t,ch);cin>>ch;break;case '>':char x,y,z;x=Popstack(op_t,x);y=Popstack(op_n,y);z=Popstack(op_n,z);Pushstack(op_n,operate(z,x,y));break;case '=':p=Popstack(op_t,p);cin>>ch;break;}}}cout<<"\t表达式结果是："<<Gettop(op_n)<<endl;return 0;}int Initstack(OPND &op_n,OPTR &op_t){op_n.base=new char[MAXSIZE];op_t.base=new char[MAXSIZE];if((op_n.base==NULL) || (op_t.base==NULL)){exit(1);}op_n.top=op_n.base;op_t.top=op_t.base;op_n.num=MAXSIZE;op_t.c=MAXSIZE;return 0;}void Pushstack(OPND &op_n,char ch){if(op_n.top-op_n.base==op_n.num){return;}*op_n.top++=ch;cout<<ch<<" 入数字栈"<<endl;}void Pushstack(OPTR &op_t,char ch){if(op_t.top-op_t.base==op_t.c){return;}*op_t.top++=ch;cout<<ch<<" 入操作符"<<endl;}char Popstack(OPND &op_n,char ch)if(op_n.top==op_n.base){exit(1);}ch=*--op_n.top;cout<<ch<<" 出数字栈"<<endl;return ch;}char Popstack(OPTR &op_t,char ch){if(op_t.top==op_t.base){exit(1);}ch=*--op_t.top;cout<<ch<<" 出字符栈"<<endl;return ch;}char Gettop(OPTR op_t){char x;if(op_t.top==op_t.base){exit(1);}x=*(op_t.top-1);cout<<"得到操作符栈顶"<<x<<endl;return x;}char Gettop(OPND op_n){char x;if(op_n.top==op_n.base){exit(1);}x=*(op_n.top-1);cout<<"得到操作数栈顶"<<x<<endl;return x;}int In(char ch)if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#') {return 1;}else{return 0;}}char Precede(char x,char y){if(x=='+' || x=='-'){if(y=='+' || y=='-' || y==')' || y=='#'){return '>';}else{return '<';}}if(x=='*'||x=='/'){if(y=='('){return '<';}else{return '>';}}if(x=='('){if(y==')'){return '=';}else if(y=='+'||y=='-'||y=='*'||y=='/'||y=='('){return '<';}}if(x==')'){if(y!='('){return '>';}}if(x=='#'){if(y=='#'){return '=';}else if(y!=')'){return '<';}}}char operate(char z,char x,char y) {if(x=='+'){return (z-'0') + (y-'0')+48;}if(x=='-'){return (z-'0') - (y-'0')+48;}if(x=='*'){return (z-'0')* (y-'0')+48;}if(x=='/'){return (z-'0')/ (y-'0')+48;}}*//*#include<iostream>using namespace std;int main(){char a[10];char *b[10];char **c[10];return 0;}*//*#include<iostream>using namespace std;char f(char x,char y){return (x-'0') * (y-'0')+48;}int main(){char a='3',b='5';char p=f(a,b);cout<<p<<endl;return 0;}*///数列出队/*#include<iostream>#include<stdlib.h>using namespace std;typedef struct Qnode{int num;struct Qnode *next;}Qnode,*Queueptr;typedef struct{Queueptr front;Queueptr rear;}LinkQueue;int InitQueue(LinkQueue &Q);void EnQueue(LinkQueue &Q,int x); int DeQueue(LinkQueue &Q,int p); int main(){LinkQueue Q;InitQueue(Q);int x,i,y,num=0,e;cout<<"请输入总人数:";cin>>x;for(i=1;i<=x;i++){EnQueue(Q,i);}cout<<"请输入第几个数淘汰:";cin>>y;{for(i=0;i<y;i++){if(i!=y-1){e=DeQueue(Q,e);EnQueue(Q,e);}else{DeQueue(Q,e);num++;}}if(num==x-1){break;}}e=DeQueue(Q,e);cout<<"最后剩下的是："<<e<<endl;return 0;}int InitQueue(LinkQueue &Q){Q.front=new Qnode;Q.rear=Q.front;if(Q.front==NULL){exit(1);}Q.front->next=NULL;}void EnQueue(LinkQueue &Q,int x){Qnode *p=new Qnode;if(!p){exit(1);}p->num=x;p->next=NULL;Q.rear->next=p;}int DeQueue(LinkQueue &Q,int e) {Qnode *p;if(Q.rear==Q.front){exit(0);}p=Q.front->next;e=p->num;Q.front->next=p->next;if(Q.rear==p){Q.front=Q.rear;}delete p;return e;}*//*二叉树#include<iostream>#include<stdlib.h>using namespace std;typedef struct BiTNode{char date;struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;void CreateBiTree(BiTree &T);int Depth(BiTree T);int NodeCount(BiTree T);int LeavesNodeCount(BiTree T);int PreOrderTraverse(BiTree T);int InOrderTraverse(BiTree T);int PostOrderTraverse(BiTree T); int main(){BiTree T;CreateBiTree(T);cout<<"二叉树的深度为："<<Depth(T)<<endl;cout<<"二叉树中结点个数为："<<NodeCount(T)<<endl;cout<<"二叉树中叶子结点个数为："<<LeavesNodeCount(T)<<endl;cout<<"先序遍历：";PreOrderTraverse(T);cout<<"\n中序遍历：";InOrderTraverse(T);cout<<"\n后序遍历：";PostOrderTraverse(T);cout<<endl;return 0;}void CreateBiTree(BiTree &T){cout<<"请为该节点赋值:";char ch;cin>>ch;if(ch=='#'){T=NULL;}else{T =new BiTNode;T->date=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}}int Depth(BiTree T){int m,n;if(T==NULL){return 0;}else{m=Depth(T->lchild);n=Depth(T->rchild);if(m>n){return m+1;}else{return n+1;}}}int NodeCount(BiTree T){if(T==NULL){return 0;}else{return NodeCount(T->lchild)+NodeCount(T->rchild)+1;}}int LeavesNodeCount(BiTree T){if(T==NULL){return 0;}else if(T->lchild==NULL && T->rchild==NULL){return 1;}else{return LeavesNodeCount(T->lchild)+LeavesNodeCount(T->rchild);}}int PreOrderTraverse(BiTree T){if(T!=NULL){cout<<T->date;PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}int InOrderTraverse(BiTree T){if(T!=NULL){InOrderTraverse(T->lchild);cout<<T->date;InOrderTraverse(T->rchild);}}int PostOrderTraverse(BiTree T){if(T!=NULL){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);cout<<T->date;}}请为该节点赋值:-请为该节点赋值:+请为该节点赋值:a请为该节点赋值:#请为该节点赋值:#请为该节点赋值:*请为该节点赋值:b请为该节点赋值:#请为该节点赋值:#请为该节点赋值:-请为该节点赋值:c请为该节点赋值:#请为该节点赋值:#请为该节点赋值:d请为该节点赋值:#请为该节点赋值:#请为该节点赋值:/请为该节点赋值:e请为该节点赋值:#请为该节点赋值:#请为该节点赋值:f请为该节点赋值:#请为该节点赋值:#二叉树的深度为：5二叉树中结点个数为：11二叉树中叶子结点个数为：6先序遍历：-+a*b-cd/ef中序遍历：a+b*c-d-e/f后序遍历：abcd-*+ef/-Process returned 0 (0x0) execution time : 76.214 s Press any key to continue.*//*#include<iostream>#include<stdlib.h>#include<string.h>using namespace std;typedef struct{int weiget;int parent,lchild,rchild;}HTNode,*HuffmanTree;typedef char** HuffmanCode;void creat(HuffmanTree &HT,int n);void Select(HuffmanTree HT,int k,int &min1,int &min2); void creatcode(HuffmanTree HT,HuffmanCode &HC,int n); int min(HuffmanTree HT,int k);int main(){int n;cout<<"请输入叶子节点的个数:";cin>>n;HuffmanTree HT;creat(HT,n);HuffmanCode HC;creatcode(HT,HC,n);return 0;}void creat(HuffmanTree &HT,int n){if(n<1){exit(1);}int m=2*n-1,i;HT=new HTNode[m+1];for( i=1;i<=m;i++){HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}for(i=1;i<=n;i++){cout<<"请输入权值:";cin>>HT[i].weiget;}int s1,s2;for(i=n+1;i<=m;i++) //通过n-1次选择来合并创建{Select(HT,i-1,s1,s2);HT[s1].parent=i; //赋值，作为删除的标记HT[s2].parent=i;cout<<"s1:"<<s1<<" s2:"<<s2<<endl;HT[i].lchild=s1; //生成新节点HT[i].rchild=s2;HT[i].weiget=HT[s1].weiget+HT[s2].weiget;}}void Select(HuffmanTree HT,int k,int &min1,int &min2){min1=min(HT,k);min2=min(HT,k);}int min(HuffmanTree HT,int k){int i=0;int min;//存放weight最小且parent为-1的元素的序号int min_wei;//存放权值while(HT[i].parent!=0){i++;}min_wei=HT[i].weiget;min=i;for(;i<=k;i++){if(HT[i].weiget<min_wei && HT[i].parent==0){min_wei=HT[i].weiget;min=i;}}HT[min].parent=1;return min;}void creatcode(HuffmanTree HT,HuffmanCode &HC,int n){HC =new char *[n+1];char *cd=new char[n];cd[n-1]='\0';int i,start;//start指向最后，即编码结束符的位置int current,father;for(i=1;i<=n;i++){start=n-1;current=i;father=HT[i].parent;while(father!=0){--start;if(HT[father].lchild==current){cd[start]='0';}else{cd[start]='1';}current=father;father=HT[father].parent;}HC[i]=new char[n-start];strcpy(HC[i],&cd[start]);cout<<HT[i].weiget<<"对应的编码是："<<HC[i]<<endl;}delete cd;}请输入叶子节点的个数:5请输入权值:1请输入权值:2请输入权值:3请输入权值:4请输入权值:5s1:1 s2:2s1:3 s2:6s1:4 s2:5s1:7 s2:81对应的编码是：0102对应的编码是：0113对应的编码是：004对应的编码是：105对应的编码是：11Process returned 0 (0x0) execution time : 4.003 s Press any key to continue.*///折半查找#include<iostream>#include<stdio.h>using namespace std;#define ENDFLAG 10000typedef int KeyType;typedef char* InfoType;typedef struct{KeyType key;InfoType otherinfo;}ElemType;typedef struct{ElemType *R;int length;}SSTable;void CreateSTable(SSTable &ST,int n){int i;ST.R=new ElemType[n+1];for(i=1;i<=n;i++){cout<<"请输入"<<i<<"个测试数据：";cin>>ST.R[i].key;}ST.length=n;}int Search_Bin1(SSTable ST,KeyType key){int low,high,mid;low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if(key==ST.R[mid].key){return mid;}else if(key<ST.R[mid].key){high=mid-1;}else{low=mid+1;}}return 0;}int Search_Bin2(SSTable ST,int low,int high,KeyType key) {int mid;if(low>high){return 0;}mid=(low+high)/2;printf("%d+++++",key==ST.R[mid].key);if(key==ST.R[mid].key){return mid;}else if(key<ST.R[mid].key){return Search_Bin2(ST,low,mid-1,key);}else{return Search_Bin2(ST,mid+1,high,key);}}int main(){int n;KeyType key;SSTable ST;cout<<"请输入静态查找表长：";cin>>n;CreateSTable(ST,n);cout<<"请输入待查记录的关键字：";cin>>key;cout<<"Search_Bin1算法计算的位置为："<<Search_Bin1(ST,key)<<endl;cout<<"Search_Bin2算法计算的位置为："<<Search_Bin2(ST,1,ST.length,key)<<endl;return 0;}/*请输入静态查找表长：5请输入1个测试数据：1请输入2个测试数据：2请输入3个测试数据：3请输入4个测试数据：4请输入5个测试数据：5请输入待查记录的关键字：3Search_Bin1算法计算的位置为：3Search_Bin2算法计算的位置为：3Process returned 0 (0x0) execution time : 8.620 sPress any key to continue.*//*#include<iostream>using namespace std;typedef struct{int key;}ElemType;typedef struct BSTNode{ElemType date;struct BSTNode *lchild,*rchild;}BSTNode,*BSTree;void Create(BSTree &T);void Insert(BSTree &T,ElemType e);int InOrderTraverse(BSTree T);int main(){BSTree T;Create(T);InOrderTraverse(T);cout<<"\n中序遍历：";return 0;}void Create(BSTree &T){T=NULL;ElemType e;cout<<"请为节点赋值:(0为结束条件)";cin>>e.key;while(e.key!=0){Insert(T,e);cout<<"请为节点赋值:(0为结束条件)";cin>>e.key;}}void Insert(BSTree &T,ElemType e){if(!T){BSTree S;S=new BSTNode;S->date=e;S->lchild=NULL;S->rchild=NULL;T=S;}else if(e.key<T->date.key){Insert(T->lchild,e);}else{Insert(T->rchild,e);}}int InOrderTraverse(BSTree T){if(T!=NULL){InOrderTraverse(T->lchild);cout<<T->date.key<<" ";InOrderTraverse(T->rchild);}return 0;}请为节点赋值:(0为结束条件)12请为节点赋值:(0为结束条件)7请为节点赋值:(0为结束条件)17请为节点赋值:(0为结束条件)11请为节点赋值:(0为结束条件)16请为节点赋值:(0为结束条件)2请为节点赋值:(0为结束条件)13请为节点赋值:(0为结束条件)9请为节点赋值:(0为结束条件)21请为节点赋值:(0为结束条件)4请为节点赋值:(0为结束条件)02 4 7 9 11 12 13 16 17 21中序遍历：Process returned 0 (0x0) execution time : 23.808 s Press any key to continue.*/。

第一篇：串-数据结构实验报告【源程序】：#include #include #include void choose(char *s, int i,int m,char *t);//i位置截取m个字符函数void main() //主函数{ char *s,*t; int i,sl,m;s=(char *)malloc(100*sizeof(char));t=(char *)malloc(100*sizeof(char));printf("\n 输入主字符串s=?"); gets(s); printf("\n s=%s\n",s);printf("\n 输入位置i=?"); scanf("%d",&i); printf("\n i=%d\n",i);printf("\n 输入字符个数m=?"); scanf("%d",&m); printf("\n m=%d\n",m);sl=strlen(s);if(i>sl) printf("i位置出错\n");else if(i+m>sl+1) printf("m位置出错\n");else{choose(s,i,m,t);printf("\n 子串为t=%s\n",t);} } //end_main void choose(char *s, int i,int m,char *t) { int n;int j=0; for(n=i;n三.实验结论及分析串的存储结构包含有顺序存储结构和链式存储结构。

在串的顺序存储结构中，表示串的长度通常有两种方法：一种方法是设置一个串的长度参数，其优点在于便于在算法中用长度参数控制循环过程；另一种方法是在串值得末尾添加结束标记，此种方法的优点在于便于系统自动实现。

《数据结构》课程实验指导《数据结构》实验教学大纲课程代码：0806523006 开课学期：3 开课专业：信息管理与信息系统总学时/实验学时：64/16 总学分/实验学分：3.5/0.5一、课程简介数据结构是计算机各专业的重要技术基础课。

在计算机科学中，数据结构不仅是一般程序设计的基础，而且是编译原理、操作系统、数据库系统及其它系统程序和大型应用程序开发的重要基础。

数据结构课程主要讨论各种主要数据结构的特点、计算机内的表示方法、处理数据的算法以及对算法性能的分析。

通过对本课程的系统学习使学生掌握各种数据结构的特点、存储表示、运算的原理和方法，学会从问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储机构及其相应的操作算法，并初步掌握时间和空间分析技术。

另一方面，本课程的学习过程也是进行复杂程序设计的训练过程，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。

二、实验的地位、作用和目的数据结构是一门实践性较强的基础课程，本课程实验主要是着眼于原理和应用的结合，通过实验，一方面能使学生学会把书上学到的知识用于解决实际问题，加强培养学生如何根据计算机所处理对象的特点来组织数据存储和编写性能好的操作算法的能力，为以后相关课程的学习和大型软件的开发打下扎实的基础。

另一方面使书上的知识变活，起到深化理解和灵活掌握教学内容的目的。

三、实验方式与基本要求实验方式是上机编写完成实验项目指定功能的程序，并调试、运行，最终得出正确结果。

具体实验要求如下：1.问题分析充分地分析和理解问题本身，弄清要求，包括功能要求、性能要求、设计要求和约束，以及基本数据特性、数据间联系等等。

2.数据结构设计针对要解决的问题，考虑各种可能的数据结构，并且力求从中选出最佳方案（必须连同算法实现一起考虑），确定主要的数据结构和全程变量。

对引入的每种数据结构和全程变量要详细说明其功用、初值和操作的特点。

约瑟夫问题实验报告（文章一）：约瑟夫问题数据结构实验报告中南民族大学管理学院学生实验报告实验项目: 约瑟夫问题课程名称：数据结构年级：专业：信息管理与信息系统指导教师：实验地点：管理学院综合实验室完成日期：小组成员：学年度第（一）、实验目的（1）掌握线性表表示和实现；（2）学会定义抽象数据类型；（3）学会分析问题，设计适当的解决方案；（二）、实验内容【问题描述】：编号为1,2,…,n 的n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。

一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自 1 开始顺序报数，报到m 时停止报数。

报m 的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从1 报数，如此下去，直至所有人全部出列为止。

试设计一个程序求出出列顺序。

【基本要求】：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。

【测试数据】：m 的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。

（三）、实验步骤（一）需求分析对于这个程序来说，首先要确定构造链表时所用的方法。

当数到m 时一个人就出列，也即删除这个节点，同时建立这个节点的前节点与后节点的联系。

由于是循环计数，所以才采用循环列表这个线性表方式。

程序存储结构利用单循环链表存储结构存储约瑟夫数据（即n个人的编码等），模拟约瑟夫的显示过程，按照出列的顺序显示个人的标号。

编号为1,2,?,n 的n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。

一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1 开始顺序报数，报到m 时停止报数。

报m 的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从1 报数，如此下去，直至所有人全部出列为止。

试设计一个程序求出出列顺序。

基本要求是利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。

数据结构实验报告-实验⼀顺序表、单链表基本操作的实现实验⼀顺序表、单链表基本操作的实现l 实验⽬的1、顺序表（1）掌握线性表的基本运算。

（2）掌握顺序存储的概念，学会对顺序存储数据结构进⾏操作。

（3）加深对顺序存储数据结构的理解，逐步培养解决实际问题的编程能⼒。

l 实验内容1、顺序表1、编写线性表基本操作函数：（1）InitList(LIST *L,int ms)初始化线性表；（2）InsertList(LIST *L,int item,int rc)向线性表的指定位置插⼊元素；（3）DeleteList1(LIST *L,int item)删除指定元素值的线性表记录；（4）DeleteList2(LIST *L,int rc)删除指定位置的线性表记录；（5）FindList(LIST *L,int item)查找线性表的元素；（6）OutputList(LIST *L)输出线性表元素；2、调⽤上述函数实现下列操作：（1）初始化线性表；（2）调⽤插⼊函数建⽴⼀个线性表；（3）在线性表中寻找指定的元素；（4）在线性表中删除指定值的元素；（5）在线性表中删除指定位置的元素；（6）遍历并输出线性表；l 实验结果1、顺序表（1）流程图（2）程序运⾏主要结果截图（3）程序源代码#include<stdio.h>#include<stdlib.h>#include<malloc.h>struct LinearList/*定义线性表结构*/{int *list; /*存线性表元素*/int size; /*存线性表长度*/int Maxsize; /*存list数组元素的个数*/};typedef struct LinearList LIST;void InitList(LIST *L,int ms)/*初始化线性表*/{if((L->list=(int*)malloc(ms*sizeof(int)))==NULL){printf("内存申请错误");exit(1);}L->size=0;L->Maxsize=ms;}int InsertList(LIST *L,int item,int rc)/*item记录值；rc插⼊位置*/ {int i;if(L->size==L->Maxsize)/*线性表已满*/return -1;if(rc<0)rc=0;if(rc>L->size)rc=L->size;for(i=L->size-1;i>=rc;i--)/*将线性表元素后移*/L->list[i+=1]=L->list[i];L->list[rc]=item;L->size++;return0;}void OutputList(LIST *L)/*输出线性表元素*/{int i;printf("%d",L->list[i]);printf("\n");}int FindList(LIST *L,int item)/*查找线性元素，返回值>=0为元素的位置，返回-1为没找到*/ {int i;for(i=0;i<L->size;i++)if(item==L->list[i])return i;return -1;}int DeleteList1(LIST *L,int item)/*删除指定元素值得线性表记录，返回值为>=0为删除成功*/ {int i,n;for(i=0;i<L->size;i++)if(item==L->list[i])break;if(i<L->size){for(n=i;n<L->size-1;n++)L->list[n]=L->list[n+1];L->size--;return i;}return -1;}int DeleteList2(LIST *L,int rc)/*删除指定位置的线性表记录*/{int i,n;if(rc<0||rc>=L->size)return -1;for(n=rc;n<L->size-1;n++)L->list[n]=L->list[n+1];L->size--;return0;}int main(){LIST LL;int i,r;printf("list addr=%p\tsize=%d\tMaxsize=%d\n",LL.list,LL.size,LL.Maxsize);printf("list addr=%p\tsize=%d\tMaxsize=%d\n",LL.list,LL.list,LL.Maxsize);while(1){printf("请输⼊元素值，输⼊0结束插⼊操作:");fflush(stdin);/*清空标准输⼊缓冲区*/scanf("%d",&i);if(i==0)break;printf("请输⼊插⼊位置：");scanf("%d",&r);InsertList(&LL,i,r-1);printf("线性表为：");OutputList(&LL);}while(1){printf("请输⼊查找元素值，输⼊0结束查找操作：");fflush(stdin);/*清空标准输⼊缓冲区*/scanf("%d ",&i);if(i==0)break;r=FindList(&LL,i);if(r<0)printf("没有找到\n");elseprintf("有符合条件的元素，位置为：%d\n",r+1);}while(1){printf("请输⼊删除元素值，输⼊0结束查找操作：");fflush(stdin);/*清楚标准缓存区*/scanf("%d",&i);if(i==0)break;r=DeleteList1(&LL,i);if(i<0)printf("没有找到\n");else{printf("有符合条件的元素，位置为：%d\n线性表为：",r+1);OutputList(&LL);}while(1){printf("请输⼊删除元素位置，输⼊0结束查找操作：");fflush(stdin);/*清楚标准输⼊缓冲区*/scanf("%d",&r);if(r==0)break;i=DeleteList2(&LL,r-1);if(i<0)printf("位置越界\n");else{printf("线性表为：");OutputList(&LL);}}}链表基本操作l 实验⽬的2、链表（1）掌握链表的概念，学会对链表进⾏操作。

数据结构实验源代码【附】数据结构实验源代码范本一、实验背景与目的1.1 实验背景在计算机科学中，数据结构是指数据元素之间的关系，以及为操作这些数据元素所提供的方法。

数据结构对于程序的设计和性能优化具有重要影响。

1.2 实验目的本实验旨在通过编写和实现不同的数据结构，加深学生对数据结构的理解，掌握基本的数据结构操作方法。

二、实验内容2.1 线性表2.1.1 顺序表2.1.1.1 初始化顺序表2.1.1.2 插入元素到顺序表2.1.1.3 删除顺序表中的元素2.1.1.4 遍历顺序表2.1.1.5 查找指定元素在顺序表中的位置2.1.2 链表2.1.2.1 初始化链表2.1.2.2 插入元素到链表2.1.2.3 删除链表中的元素2.1.2.4 遍历链表2.1.2.5 查找指定元素在链表中的位置2.2 栈2.2.1 初始化栈2.2.2 进栈操作2.2.3 出栈操作2.2.4 获取栈顶元素2.2.5 判断栈是否为空2.3 队列2.3.1 初始化队列2.3.2 入队操作2.3.3 出队操作2.3.4 获取队首元素2.3.5 判断队列是否为空三、实验步骤3.1 线性表实现在实现顺序表和链表时，首先需要定义数据结构和所需的操作函数。

然后进行初始化、添加元素、删除元素等操作。

最后进行遍历和查找操作，并检验实验结果是否符合预期。

3.2 栈实现栈的实现过程与线性表类似，需要定义栈的数据结构和所需的函数，然后进行初始化、进栈、出栈等操作。

3.3 队列实现队列的实现也与线性表类似，需要定义队列的数据结构和函数，进行初始化、入队、出队等操作。

四、数据结构实验源代码以下是实验代码的源代码范本，包括线性表、栈和队列的实现。

（代码略，如需获取，请查看附件）五、附件本文档附带的附件为数据结构实验源代码。

六、法律名词及注释6.1 数据结构：计算机科学中，数据结构是指数据元素之间的关系，以及为操作这些数据元素所提供的方法。

6.2 顺序表：一种物理上相邻的存储结构，元素按照顺序依次存放。

数据结构实验课教案数据结构教案实验一：线性表的顺序表示与实现实验学时：2学时一．实验目的：1．掌握线性表的顺序存储结构；2．掌握在顺序表上进行的插入、删除、查找、修改等操作。

二．实验内容：1．分别建立顺序表，并输入初始数据；2．对顺序表分别编写插入、删除、查找、修改等函数。

三．实验重点：顺序表的建立及操作。

四．实验要求：1．用C语言编写程序源代码；2．要分别完成建立、插入、删除、查找、修改五种功能。

3．源程序必须编译调试成功，独立完成。

五．实验器材：一个装有C语言编译环境的计算机。

六．实验步骤：顺序表：1．定义头文件和顺序表的存储结构类型等 #define ok 1 #define error 0 #define overflow 0 #define null 0 #include #include #define list_init_size 100 #define listincrement 10 typedef int elemtype; typedef int status; typedef struct{ elemtype *elem; int length; int listsize; }sqlist;1 2．编写构造空顺序表的函数status listinit(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; }3．编写对顺序表进行插入操作的函数： status listinsert(sqlist *l,int i,elemtype e) { elemtype *newbase,*q,*p; if(ilistlength(*l)+1)return error; if(l->length==l->listsize){ newbase=(elemtype *)realloc(l->elem,(l->listsize+listincrement)*sizeof(elemtype));if(!newbase)return overflow;l->listsize+=listincrement;} q=&(l->elem[i-1]); for(p=&(l->elem[l->length])-1;p>=q;--p)*(p+1)=*p; *q=e; ++l->length; return ok; }4．编写对顺序表进行删除操作的函数：status listdelete(sqlist *l,int i,elemtype *e) { elemtype *p,*q; if(il->length)return error; p=&(l->elem[i-1]); *e=*p; q=l->elem+l->length-1; for(++p;p*(p-1)=*p; --l->length;2 return ok; }5．编写对顺序表进行查找操作的函数： status getelem(sqlist l,int i,elemtype *e) { if(ilistlength(l)) return error; *e=[i-1]; return ok; }6．编写对顺序表进行修改操作的函数： status locateelem(sqlist l,elemtype e) { int i; for(i=0;iif([i]==e)return i+1; return 0; } 7．编写实现两个线性表的归并操作的函数 void mergelist(sqlist la,sqlist lb,sqlist *lc) { int i,j,k; intla_len,lb_len; elemtype ai,bj; i=j=1; k=0; listinit(lc); la_len=listlength(la); lb_len=listlength(lb); while(i{listinsert(lc,++k,ai);++i;} else{listinsert(lc,++k,bj);++j;} } while(iwhile(j{ getelem(lb,j++,&bj); listinsert(lc,++k,bj);} }8．销毁线性表、清空线性表、判空、求表长等 status destroylist(sqlist *l) { if(l->elem) free(l->elem),l->elem=null; return ok; }status clearlist(sqlist *l) { l->length=0; return ok; }status listempty(sqlist l) { return(==0); }status listlength(sqlist l) { return ; }9．打印线性表4 void print(sqlist l) { int i; printf(\”\\nlist: \”); for(i=0;i10．编写主函数 void main() { int i; int n; elemtype a; sqlist l,la,lb,lc; clrscr(); listinit(&l); listinit(&la); listinit(&lb);printf(\”please input list number\”); scanf(\”%d\”,&n); printf(\”\\n\”); for(i=0;iscanf(\”%d\”,&a);listinsert(&l,i+1,a); } print(l); printf(\”\\nlist length:%d\”,listlength(l));getelem(l,4,&a); printf(\”\\ngetelem(l,4,&a),%d\”,a);listdelete(&l,3,&a); printf(\”\\nlistdelete(&l,3,&a),%d\”,a); print(l);printf(\”\\ninput list la\”);for(i=0;iscanf(\”%d\”,&a);listinsert(&la,i+1,a); } printf(\”\\ninput list lb\”);5 for(i=0;iscanf(\”%d\”,&a);listinsert(&lb,i+1,a); } mergelist(la,lb,&lc); print(la);print(lb);print(lc); }6实验二：链表实验学时：2学时一．实验目的：11．掌握单、双向链表的存储结构；12．掌握在单、双向链表上进行的插入、删除、查找、修改等操作。