数据结构实验指导

1、实验 1序列表和链表一、实验目的1 .掌握线性表格中元素的前身和后续概念。2 .掌握建立序列表和链表、插入元素和删除元素的算法。 3 .分析相应的线性表算法的时间复杂度。 4 .了解序列表和链表数据结构的特点（优缺点）。二、实验预演解释以下概念1。线性表格 :3 .序列表 :4 .链接列表 :三。实验内容和要求1 .阅读以下程序，并在水平线处填写该功能的基本功能。运行程序，写下结果。# 包含 # 包括 # define ERROR 0# 定义好1# 定义INIT _ SIZE 5/* # 定义 INCREM 5typedef int 元素类型；当最初分配的序列表长度*/* 溢出时，序列表长度的

2、增量*/* 定义类型 */typedef 结构 Sqlist元素类型 * 列表； /*整数长度； /*int listsize/* 列表；存储空间的基址*/ 序列表的当前长度*/ 当前分配的存储空间 */int InitList _ sq(SqList * L) ； /* */ int CreateList_sq(Sqlist *L ， int n)； /* */ int ListInsert_sq(Sqlist *L ， int i ， ElEMType e)； /* */int PrintList _ sq(SqList * L) ； /*输出顺序表 的元素 */intlistdelete

3、 _ sq (sqlist * l ， inti) ； /*删除第 I 个元素 */int list locate(SQL list * l ， elem type)； /*查找值为 E 的元素 */int InitList_sq(Sqlist *L)列表 =(ElEMType *)malloc(INIT _ SIZE * Sizeof(ElEMType) ；1如果( ！返回错误；l 长度= 0；列表大小 =初始化_大小；返回 “确定 ” ；/*InitList*/int CreateList_sq(Sqlist *L ， int n)e 型。int I ；对于 (I = 0 ； I n ；

4、i+)printf( 输入数据“%d” ， I+1) ； scanf( “%、 d”& e) ；如果(！ ListInsert_sq(L, i+1 , e)返回错误；返回 “确定 ” ；/* 创建列表 */* 输出顺序表中的元素*/int PrintList_sq(Sqlist *L)int I ；对于 (I = 1 ； i 长度； i+)printf(%5d ，左列表 i1) ；返回 “确定 ” ；/* 打印列表 */ int ListInsert_sq（Sqlist *L ， int i ， ElemType e）int k；if（iL 长度 +1）返回 ERROR如果 （长度 =列表大小

5、）列表 =（元素类型*）实值列表，（INIT _ SIZE+INCREAM）* Sizeof（ElEMTYPe） ；如果 （ ！列表）返回 ERROR列表大小 += INCREMM ；对于 （k=L 长度 1； k = i1k）名单 +1= 名单 k ；列出 i1= e ；长度 +；返回 “确定 ” ；/* 列表插入 */2/* 删除序列表中的第I 个元素 */int ListDelete_sq（Sqlist *L ， int i）if（iL 长度 ）返回 ERROR如果 （L 长度 = 0）返回 ERROR对于 (int j = I ；长度； j+) 排行榜；长度；返回 “确定 ” ；/*

6、在序列表中找到指定的值元素，并返回其序列号*/int ListLocate(Sqlist *L ， ElemType e)整数长度 = 1 长度；对于 (int I = 0 ； I 长度； i+)如果(L 列表0 = e)返回I;返回 ERRORint main()Sqlist sl。int n ， m， k；printf( 请输入 n:) ； /* scanf(%d ， & n) ；如果 (n0)输入订单表中的元素数量*/printf( n1 CREAte Sqlist: n ) ； initLiST _ sq(& sl) ； CreateList_sq(&sl， n) ；printf( N

7、2 Print Sqlist: n ) ；打印列表_ sq(& sl)；printf( n请输入插入位置和数据：(位置，数据) n ); scanf(%d、d 、&m和k);列表插 入 _sq(&sl ， m， k) ； printf( n3Print Sqlist: n ) ；打印列表_ sq(& sl) ； printf( n ) ； 其他printf(“ ERRO；”)R返回 0；3l运行结果算法分析l2.为问题 1 添加删除和搜索功能，并为主功能添加代码以验证算法的正确性。删除算法代码运行结果l算法分析l查找算法代码:4l 运行结果l 算法分析3.阅读以下程序，并在水平线处填写该功能的

8、基本功能。运行程序，写下结果。 # include # include #定义错误0 #定义确定1typedef int元素类型；/*定义表格元素的类型*/typedef结构 LNode/* ElemType 数据；线性表的单链表存储*/结构 LNode * nextLNode ， *链接表；链接表创建列表(int n)； /* */无效打印列表；/*输出头节点*/intgetelem (linklistl , inti, elemtype * e)的单个链表的所有元素； /* */linkLiST CreateList(int n) LNode * p ， *q ， * headint I

9、；head =(LinkList)malloc(size of(LNode) ； p = head对于 (I = 0 ； I next =KUIiL;printf（inputscanf（ , d&q 数据）；/*q 下一个二空；/*p 下一个=q； /*p = q; 返回头；/*创建列表*/输入元素值*/节点指针字段为空*/新节点连接在表的末尾*/int插入列表（链接列表L,元素类型e, int I）/插入到元素之前LNode * p = L；5int j = 0 ；而（p & j i1 ）p = p 下一步；j+;如果（！ p II ji）返回ERRORLNode* s =（链接表）mall

10、oc（大小为（LnODE）；s也据二e；s 下一个 =p 下一个；p 下一个=s；返回 “确定 ” ；int删除列表（链表L,元素类型& e, int i）/ 删除第 I 个元素，并返回它的值LNode * p = L ；int j = 0 ；而 （p 下一个 & i1 ）p = p 下一步；j+;如果 （！ （p 下一个）& j i1）返回 ERROR下一步；p 下一个= q 下一个；e = q 数据；自由（q）；返回 “确定 ” ；无效打印列表（链接表 1）LNode * p ；p=L 下一个； /*p指向单个链表的第一个元素 */同时 （p！ =空）printf（“ %，5dp” 数据

11、） ；p=p 下一步；int GetElem(链表 L, int i , ElemType *e)LNode * p； int j = 1 ；p=L 下一个；而(p & j 下一步；j+;6如果 ( ！ p|ji)返回 ERROR*e=p 数据；返回 “确定 ” ；/*GetElem*/int main()lint n, I; e型。链表 L =空； /*定义指向单个链表的指针 */ printf( 请输入 “n: “) ； /*输入单个链表中的元素个数*/ scanf(%d ， & n)；如果 (n0)printf( n1CREAte LinkList: n ) ；l = 创建列表 (n)

12、；printf( N2 打印链接列表: n ) ；打印列表 (L) ；printf( n3GetElem from LinkList: n ) ； printf( input I = ) ；scanf(“ %、 d”& I) ；如果 （元素 （L ， I， e）printf（否%i 是%（1,即）；其他printf（ 不存在“ ”） ； 其他printf（ “ ERRO；”）R返回 0；运行结果算法分析l4.在问题3 中增加插入功能和删除功能。主要功能用代码补充，以验证算法的正确性。插入算法代码:7运行结果l算法分析l删除算法代码:运行结果l算法分析l以下是选定的实验:85、循环链表的应用（约

13、瑟夫环回问题） n个数据元素形成一个环，从环中的任何位置开始计数，从表中取出元素直到 m,并重复上述过程直到表中只剩下一个元素。提示 : 一个没有头节点的循环链表用于存储 N 个元素。 l 算法代码6.设置一个带有头节点的链表。设计算法将只为表中具有相同值的元素保留一个节点。提示:指针 P 从链表的第一个元素开始，使用指针 Q 从指针 P 的位置向后搜索整个链表，并删除具有相同值的元素。指针p 继续指向下一个元素，并开始下一轮删除，直到 p = = null 为 to，从而以相同的值完成整个链表元素的删除。 l 算法代码四 .实验总结V.教师的评论9实验 2 堆栈和队列一、实验目的1 .掌握烟

14、囱的结构特点及其进出烟囱的操作；2 .掌握队列的结构特征及其进出操作，掌握循环队列的特征和操作。二、实验预演解释以下概念1。序列堆栈:3 .链栈 :4 .循环队列 :5 .连锁团队三。实验内容和要求1,阅读下面程序，将函数Push和函数Po口补充完整口要求输入元素序列1 2 3 4 5已，运 行结果如下所示.#include# 包括# define ERROR 0# 定义好1# define STACK_INT_SIZE 10 /* 初始存储空间分配 */ #define STACKINCREMENT 5 /* 存储空 间分配增量*/ typedef int元素类型。/*定义元素的类型*/ty

15、pedef 结构ElemType * baseElemType * topint stacksize/*当前分配的存储空间*/10 SqStack内部初始化堆栈；/*构造空堆栈*/int push(SqStack *S, elem type e /*栈*/ int Pop(栈*S,元素类型* e); /*堆栈外*/int CreateStack(SqStack * S) /* 无效打印堆栈(SqStack * S); /*int InitStack(SqStack *S)创建堆栈 */拉出堆栈和堆栈中的输出元素 */s base =(ElEMType *)malloc(STACK _ INT

16、_ SIZE * Sizeof(ElEMType) ；如果 ( ！返回错误；顶部 =底部；s 堆栈大小=堆栈 _整数 _大小；返回 “确定 ” ；/*InitStack*/int Push(SqStack *S， ElemType e)/* 推送 */int Pop(SqStack *S， ElemType *e)/*Pop*/int CreateStack(SqStack *S)int e；如果 (初始化堆栈)printf( 初始化成功！ “ n ) ；否则 printf( 初始化失败！ “ n ) ；返回 ERRORprintf( 输入数据“:(通过输入字符终止) n”) ； while(

17、scanf(“%、 d&”e)推动 (S， e)；返回 “确定 ” ；void PrintStack(SqStack *S) e 型。而 (流行音乐)printf(%3d ， e)；/* 弹出和打印*/11 int main() lSqStack ss。printf( n1 CreateTack n )；创建标签(& ss) ；printf( n2po & Print n ) ；打印堆栈(& ss) ；返回 0；算法分析 :输入元素序列 1 2 3 4 5，为什么输出序列5 4 3 2 1？堆栈的特点是什么？2 .在问题1 中的程序中，编写一个十进制到二进制转换算法函数(需要堆栈实现) ，并验

18、证其正确性。l 实施代码确认 l3 .阅读并运行程序，分析其功能。#包含 #包含 #包含 #定义M 20#define elemtype char typede酷构M; int top stacknodevoid init(stack node * ST) ；空隙推进(堆积体*st, elem type x)；无效弹出(stack node * ST)；12void init(stacknode *st) ST top = 0；void push(stacknode *st， elemtype x) 如果 (sttop=M)printf( 堆栈溢出！ “ n ) ；其他ST top = ST top+1； ST stackST top= x；void pop(stacknode *st) 如果(ST top 0)ST top；否则打印(堆栈为空！ n );int main() 查尔M ; int I;stacknode * spprintf(创建一个空堆栈！ n ); sp =(stack node *)malloc(sizeof(stack n