当前位置：文档之家 › 课程设计1 线性表及应用

课程设计1 线性表及应用

  • 格式：doc
  • 大小：261.00 KB
  • 文档页数：19

题目： 线性表及应用 内容： 题目： 线性表及应用 日期： 2011年5月25日星期三 姓名： 肖剑锋 学号：026308 一． 实习目的

帮助学生熟练掌握线性表的基本操作在两种存储结构上的实现，其中以单链表的操作和应用为重点内容。

二． 问题描述 编制一个演示单链表的建立、打印、查找、插入、删除等操作的程序。 三． 需求分析 1. 创建单链表 2. 向链表中查人数据 3. 删除链表中的数据 4. 查找链表中的内容 5. 打印内容 四． 概要设计

为了实现上述程序功能，需要定义一个简化的线性表抽象数据类型：

ADT LinearList { 数据对象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0} 结构关系：R={|ai,ai+1 ∈D} 基本操作： InitLinkList(L) 操作前提：L是一个未初始化的线性表 操作结果：将L初始化为一个空的线性表 CrtLinkList(L) 操作前提：L是一个已初始化的空表 操作结果：建立一个非空的线性表L InsLinkList(L,pos,e) 操作前提：线性表L已存在 操作结果：将元素e插入到线性表L的pos位置 DelLinkList(L,pos,e) 操作前提：线性表L已存在 操作结果：将线性表L中pos位置的元素删除， 删除的元素值通过e返回 LocLinkList(L,e) 操作前提：线性表L已存在 操作结果：在线性表L中查找元素e， 若存在，返回元素在表中的序号位置； 若不存在，返回-1 }

五． 详细设计（给出算法的伪码描述） (1).判断表长是否足够，如果不足，重新分配存储空间；

(2).从后向前，依次后移大于x的元素 for(i=L.length-1;(i>=0)&&(L.elem[i]>x);i--) L.elem[i+1]=L.elem[i]; (3).插入x到第i+1个位置，修改表长等信息。 (4).完成操作

2.顺序表的就地逆置实际只需要将对应位置的元素交换即可，即将第１个与第n个元素交换，第２个与第n-1个交换……

for(i=0;i L.elem[i]<->L.elem[n-1-i]

3.用单链表表示集合，假设集合A、B分别由链表la和lb表示，运算结果集合c由lc表示。 并：（１） 将la链表复制到lc中 （２）从前到后依次从lb中取出元素，首先判断la中是否存在相同元素，若存在，则直接取下一个元素，若不存在，则将该元素插入到lc中，再取下一个元素。 交：即找出链表la和lb中都有的元素，把他们增加到lc中 差：即把la当中存在，但是lb中没有的元素，增加到lc中。

六． 测试分析 白盒： 查看代码完整性 黑盒： 测试是否可以正确的创建，删除，插入，打印，查找等操作 七． 使用说明 点击删除键：删除1条内容 点击插入键：插入如一条信息 点击打印键：打印内容 点击查找键：查找内容 八． 附录：测试数据 测试内容 测试结果 点击删除键删除一条内容 正确 点击插入键插入一条信息 正确 点击打印键正常打印内容 正确 点击查找键正常查找内容 正确

九． 附C语言实现源码 #include #include #include

#define TURE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef int ElemType;

typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList;

void CreatSet(LinkList *L,int n) //初始化链表L，n为集合的元素个数 {ElemType x; LinkList p; *L=(LinkList)malloc(sizeof(LNode)); (*L)->next=NULL; printf("\nPlease input %d elemts:",n); while(n>0) { p=(LinkList)malloc(sizeof(LNode)); scanf("%d",&x); p->data=x; p->next=(*L)->next; (*L)->next=p; n--; } } void Output(LinkList L) //输出集合L的元素 {LinkList p; printf("["); for(p=L->next;p;p=p->next) printf("%d,",p->data); printf("]"); }

int LocateElem(LinkList L,ElemType e) //在集合L中查找元素e，若存在返回其在链表中的结点序号，若不在在返回0 {LinkList p; int i=0,loc=0; p=L->next; while(p) {i++; if(p->data==e) {loc=i;break;} p=p->next; } return(loc); }

LinkList ComSet(LinkList A,LinkList B) //求集合A、B的并集合 {LinkList C,p,q; C=(LinkList)malloc(sizeof(LNode)); C->next=NULL; for(p=A->next;p;p=p->next) {q=(LinkList)malloc(sizeof(LNode)); q->data=p->data; q->next=C->next; C->next=q; } for(p=B->next;p;p=p->next) if(!LocateElem(C,p->data)) {q=(LinkList)malloc(sizeof(LNode)); q->data=p->data; q->next=C->next; C->next=q; } return(C); }

LinkList IntSet(LinkList A,LinkList B) //交集 {LinkList C,p,q; C=(LinkList)malloc(sizeof(LNode)); C->next=NULL; for(p=A->next;p;p=p->next) if(LocateElem(B,p->data)) {q=(LinkList)malloc(sizeof(LNode)); q->data=p->data; q->next=C->next; C->next=q; } return(C); }

LinkList SubSet(LinkList A,LinkList B) //差集 {LinkList C,p,q; C=(LinkList)malloc(sizeof(LNode)); C->next=NULL; for(p=A->next;p;p=p->next) if(!LocateElem(B,p->data)) {q=(LinkList)malloc(sizeof(LNode)); q->data=p->data; q->next=C->next; C->next=q; } return(C); }

void main() {LinkList A,B,C; int n; printf("\n输入集合A的大小:"); scanf("%d",&n); CreatSet(&A,n); printf("\n输入集合B的大小:"); scanf("%d",&n); CreatSet(&B,n); printf("\n集合 A:"); Output(A); printf("\n集合 B:"); Output(B); C=ComSet(A,B); printf("\n集合A并B:"); Output(C); C=IntSet(A,B); printf("\n集合A交B:"); Output(C); C=SubSet(A,B); printf("\n集合AB的差:"); Output(C); printf("\n"); }

十．附程序运行结果截图

合集下载

C语言——线性表及其应用

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为查找的结点。

线性表的基本操作及其应用

线性表的基本操作及其应用

线性表的基本操作及其应用一、实验目的1、帮助学生复习C++语言程序设计中的知识。

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

3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。

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

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

三、概要设计各操作的具体函数实现：1.用尾插法建立带头结点的链表可任意输入元素（char 型）,void CreatList(LinkList &L){//LinkList p;L=(LinkList)malloc(sizeof(LNode));int n=0,j=0;L->next=NULL;cout<<"请输入结点个数:";cin>>n;for(int i=n;i>0;i--){LinkList p;p=(LinkList)malloc(sizeof(LNode));cout<<"请输入一个节点数据:"<<endl;cin>>p->data;p->next=L->next;L->next=p;Length++;//每增加一个数据，Length加一}}2.清空链表分析链表为空时，输出为空；当链表不为空时，清空链表，并输出原来的链表已经被清空!的字样告诉操作者，链表已为空了int ClearList(LinkList &L){if(L->next==NULL){cout<<"链表为空！";}else {{LinkList p,q;p=L->next;while(p){q=p;p=p->next;-- Length;delete q;}}cout<<"原来的链表已经被清空!!"<<endl;}return OK;}3.求链表的长度在建立链表是已经用Length着个全局变量记载建立的结点的个数，即链表的长度用cout<<Length就可以得到链表的长度：int Listlength(LinkList L){cout<<"链表长度为："<<Length<<endl;return Length;}4.链表元素的展示用函数DisplayList(LinkList L)实现，首先判断链表是否为空，当链表不为空时，在从第一个元素找到并输出，主要步骤为：LinkList p;p=L->next;cout<<"链表中的数据依次为:"<<'\t';while(p){cout<<p->data<<" ";p=p->next;}5.从链表中查找元素用函数GetElem_L(LinkList L)来实现该功能。

线性表及其应用

线性表及其应用

线性表及其应用哈尔滨工业大学计算机科学与技术学院实验报告课程名称：数据结构与算法课程类型：必修实验项目名称：线性表及其应用实验题目：算术表达式求值班级：1003201学号：姓名：设计成绩报告成绩指导老师一、实验目的1. 掌握栈的数据结构与基本操作2. 了解什么是中缀表达式和后缀表达3. 了解并掌握中缀表达式转为后缀表达式的方法4. 掌握使用栈结构求解后缀表达式的求值方法5. 提高利用计算机分析和解决复杂实际问题的能力二、实验要求及实验环境 1. 试验要求：(1)从键盘输入任意一个语法正确的（中缀）表达式，显示并保存该表达式。

(2)利用栈结构，把上述（中缀）表达式转换成后缀表达式，并显示栈的状态变化过程和所得到的后缀表达式。

(3)利用栈结构，对上述后缀表达式进行求值，并显示栈的状态变化过程和最终结果。

2.试验环境：Windows 7操作系统 Devc C++ 编译器三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系）程序中用到的数据类型的定义：char string1[100]; //存放表达式struct Stack{ //定义一个栈char data[maxlength]; int top;};typedef struct Stack stack1;stack1 output1; //存放操作符stack output1; //存放后缀表达式的数字的栈主程序流程图：弹出栈内所有元素存入结尾数组低直接压入栈中开始输入一个以字符串形式定义的运算式并保存至数组string1[100]中,声明一个运算符栈用来存放运算符指针遍历字符串数组高直接存入结尾数组中与栈顶运算符比较直接压入栈中并在结尾数组中存入空格弹出栈内与之匹配的（前的所有运算符并存结尾数组中为运算符存入空格为数字判断字符串数组每一个单元的内容为（存入空格为）将栈内元素全部存至结尾数组中弹出整型栈中的两个元素进行相应的加减乘除运算，并将运算结果重新压入栈中为运算符将空格之前到前一个空格之间的所有存入数字数组中的数字进行位数计算得到一个新的数字压入栈中将字符型转换为整型存入一个数字数组中去遍历结尾数组中的每一个元素申请一个新的整型栈用于后缀表达式计算将后缀字符串和计算得到的结构输出判断每一个元素的内容为“”为数字结束各程序模块之间的调用关系：int main() {char qianzhui[100];cout << \请输入一个语法正确的（中缀）表达式(在此过程不用输入等号)：\ gets(qianzhui);cout << \该中缀表达式为：\ cout << qianzhui<< endl;; change(qianzhui);cout << \转换为后缀表达式为：\ cout << string2<< endl;;jisuan(string2); return 0; }四、测试结果.请输入一个语法正确的（中缀）表达式(在此过程不用输入等号)：12.3*(12.34+23.54)-23.4/23.45该中缀表达式为：12.3*(12.34+23.54)-23.4/23.45 进栈元素为：* 进栈元素为：+ 出栈元素为：+ 出栈元素为：( 出栈元素为：* 进栈元素为：- 进栈元素为：/ 出栈元素为：/。

线性表及其应用

线性表及其应用

线性表（链式存储）及其应用一、实验目的1.掌握链表的结构原理、如何创建链表、如何输出结点数据、如何插入结点、如何删除结点等。

2.复习C语言，加深对C语言的理解和应用。

二、实验内容建立一个采用链式存储的线性表，表中元素为学生，每个学生信息包含姓名和学号两部分，对该表实现：①输出、②查找、③插入、④删除功能。

程序源代码：#include<malloc.h>#define NULL 0#define LEN sizeof(struct student)#include<conio.h>#include<string.h>#define A struct studentstruct student{ long num; char name[8]; struct student *next;};int count;/*―--―--―――输入函数――――――------――――――――*/ struct student *creat(){ A *head,*p,*pt;int length,i;printf("你要输入的个数:");scanf("%d",&length); count=length;for(i=1;i<=length;i++){p=(A *)malloc(LEN);if(i==1) head=pt=p; else pt->next=p;pt=p;printf("第%d个数的学号",i);scanf("%ld",&p->num);while(p->num>99999||p->num<1){printf("学号超出范围,重新输入");printf("第%d个数的学号",i);scanf("%ld",&p->num);}printf("第%d个数的姓名",i);scanf("%s",&p->name);}p->next=NULL;printf(" 你输入的数据:\n");return(head);}/*―――――-----―-――输出函数――――――--------------――――――――*/ void print(A *head){A *p;p=head;printf(" ______________________________________________\n");printf(" 有%d个学生\n",count);printf(" 学号姓名\n");if(head!=NULL){ do{printf("%23ld%24s\n",p->num,p->name);p=p->next;}while(p!=NULL);}else printf("sorry!空表");printf(" ______________________________________________\n");}/*――――――-----―-――内部数据――――――--------------――――――――*/ struct student *date(){A *head,*p1,*p2,*p3,*p4;head=(A *)malloc(LEN);if(head==NULL) printf("申请空间失败");head->next=NULL;p1=(A *)malloc(LEN);head=p1;p1->num=888;strcpy(p1->name,"Jack");p1->next=NULL;p2=(A *)malloc(LEN);p1->next=p2;p2->num=150;strcpy(p2->name,"Rose");p2->next=NULL;p3=(A *)malloc(LEN);p2->next=p3;p3->num=133;strcpy(p3->name,"Bush");p3->next=NULL;p4=(A *)malloc(LEN);p3->next=p4;p4->num=999;strcpy(p4->name,"Bush");p4->next=NULL;count=4;printf(" 内部数据:\n");return(head);}/*―――――--―-――位置插入函数――――――--------------――――――――*/ struct student *p_insert(A *head){A *p1,*p2,*inp;int place,i;printf("要插入的位置：");scanf("%d",&place);inp=(A *)malloc(LEN);printf("学号");scanf("%ld",&inp->num);while(inp->num>99999||inp->num<1){printf("学号超出范围,重新输入");printf("学号");scanf("%ld",&inp->num);}printf("姓名");scanf("%s",&inp->name);p1=head;for(i=1;i<place;i++) {p2=p1;p1=p1->next;}if(i==1){inp=p1->next;head=inp;} else {p2->next=inp;inp->next=p1;}count++;printf(" 按位置插入后结果:\n");return(head);}/*――――――-----―-――排序函数――――――--------------――――――――*/ struct student *shen_sort(A *head){A *p,*min;int i=1;long m_num;char m_name[8];p=head;min=head;for(i=1;i<=count;i++){ p=min->next;while(p!=NULL){if(p->num<min->num){m_num=p->num;p->num=min->num;min->num=m_num;strcpy(m_name,p->name);strcpy(p->name,min->name);strcpy(min->name,m_name);} p=p->next; }min=min->next;} printf(" 排序后结果:\n");return(head);}/*―――――----―-――按顺序插入函数――――――--------------――――――――*/struct student *s_insert(A *head){A *p1,*p2,*pi;head=shen_sort(head);pi=(A *)malloc(LEN);printf("插入的学号");scanf("%ld",&pi->num);while(pi->num>99999||pi->num<1){printf("学号超出范围,重新输入");printf("学号");scanf("%ld",&pi->num);}printf("姓名");scanf("%s",&pi->name);p1=head;while(pi->num>p1->num&&p1->next!=NULL){p2=p1;p1=p1->next;}if(pi->num<=p1->num){if(p1==head) head=pi; else p2->next=pi;pi->next=p1;}else {p1->next=pi;pi->next=NULL;}count++;printf(" 按顺序插入后结果:\n");return(head);}/*―――――----―-――删除函数――――――--------------――――――――*/ struct student *del(A *head){A *p1,*p2;long del_num;printf("要删除的学号");scanf("%ld",&del_num);p1=head;while(p1->num!=del_num&&p1->next!=NULL){p2=p1;p1=p1->next;}if(p1->num==del_num){if(p1==head)head=p1->next;else p2->next=p1->next;count--;printf(" 删除后结果:\n"); }else printf("学号不存在，删除失败");return(head);}/*――――-----―-――修改函数――――――--------------――――――――*/ struct student *amend(A *head){A *p;long num;printf("要修改的学号");scanf("%ld",&num);p=head;while(p->num!=num&&p->next!=NULL)p=p->next;if(p->num==num){printf("修改后的姓名");scanf("%s",&p->name);printf(" 修改后结果:\n");}else printf("学号不存在，修改失败"); return(head);}/*―――――-----―-――释放函数――――――--------------――――――――*/void free_list(A *head){A *p=head;printf("释放链表");while(p!=NULL){head=head->next;free(p);p=head;}}/*――――――-----―-――菜单函数――――――--------------――――――――*/ void menu(){printf("*****************************链表操作菜单************************************\n");printf(" 1、输入 2、输出 3、内部数据 4、按位置插入\n"); printf(" 5、排序 6、顺序插入 7、删除\n");printf(" 8、修改 0、释放链表退出\n");printf("*****************************************************************************\n");}/*―――――――---――――-----―-――主函数――――――--------------――――――――*/void main(){A *head; int m;int flag=1;menu();while(flag){printf("输入代码:");scanf("%d",&m);switch(m){case 1:head=creat();print(head);break;case 2:print(head);break;case 3:system("cls");menu();head=date();print(head);break;case 4:system("cls");menu();print(head);head=p_insert(head);print(head);break; case 5:system("cls");menu();print(head);head=shen_sort(head);print(head);break; case 6:system("cls");menu();print(head);head=s_insert(head);print(head);break; case 7:system("cls");menu();print(head);head=del(head);print(head);break;case 8:system("cls");menu();print(head);head=amend(head);print(head);break; case 0:free_list(head);flag=0;system("cls");printf("\n\n\n\n\n\n\n\n\n\n\n\n 谢谢使用\n");break; default:printf("代码错误，请重新输入\n");}}}三、调试运行结果：四、实验小结1、通过程序调试后，终于完成任务，对链表也有了更深的了解，特别是C语言中指针的概念有了更深的认识。