数据结构作业题.doc

1 简述下列术语：线性表，顺序表，链表。答：线性表是最常用且最简单的一种数据结构，一个线性表是N个数据元素的有限序列。顺序表是指用一组地址连续的储存单元依次存储线性表的数据元素。用这种方法存储的线性表简称顺序表。链表是用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。2 何时选用顺序表，何时选用链表作为线性表的存储结构合适?各自的主要优缺点是什么?答：线性表的逻辑顺序与物理顺序一致;数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。而存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。链表中结点的逻辑顺序和物理顺序不一定相同。3 在顺序表中插入和删除一个结点平均需要移动多少个结点?具体的移动次数取决于哪两个因素?答：在顺序表中插入和删除一个结点平均需要移动1个结点，具体移动次数取决于时间复杂和空间复杂程度。4 链表所表示的元素是否有序?如有序，则有序性体现于何处?链表所表示的元素是否一定要在物理上是相邻的?有序表的有序性又如何理解?答：链表元素的有序并不一定是值得有序，而是逻辑次序上的有序；链表中的元素并不需要物理位置上相邻，因为其逻辑联系已经在结点中包括了。5 设顺序表L是递增有序表，试写一算法，将x插入到L中并使L仍是递增有序表。答：using System;using System.Collections.Generic;using System.Collections;using System.Text;namespace test class arrlist_test public static ArrayList a = new ArrayList(); public static void main() do currency.write(请写入下一个值); a.Add(Console.ReadLine(); a.Sort(); while(currency .choice (); for (int i = 0; i next;while(pa!=null) pa=pa-next,i+;return i;7 写一算法将单链表中值重复的结点删除，使所得的结果链表中所有结点的值均不相同。 答：void DeleteList ( LinkList L ) ListNode *p , *q , *s; p=L-next; while( p-next&p-next-next) q=p;while (q-next) if (p-data=q-next-data) s=q-next;q-next=s-next;free(s); else q=q-next; p=p-next; 8 写一算法从一给定的向量A删除值在x到y(xy)之间的所有元素(注意：x和y是给定的参数，可以和表中的元素相同，也可以不同)。 答：#includetypedef int datatype;#define maxsize 100/*定义顺序表*/typedef struct datatype datamaxsize; int last; SeqList;/*初始化*/void init_SeqList(SeqList *L) L-last=-1;/*输入顺序表*/void input_SeqList(SeqList *L,int n) int i; L-last=0;/初始化 for(i=0;idatai); L-last=L-last+n;/*判断*/int measure(SeqList *L,int x,int y,int n) if (L-data0=L-datan-1 & x=L-datan-1 & ydata0) |/是n-1 (L-data0datan-1 & x=L-data0 & ydatan-1) return 1; else return 0;/*删除值*/int delete_list(SeqList *L,int x,int y) int i=0,j=0; while (ilast) /* if (L-datai=x) & (L-dataidatai-distence=L-datai;*/ if(L-dataidataiy) L-dataj+=L-datai; i+; /L-last-=distence; L-last=j; /printf(j=%dn,j); if (L-last=0) printf(原表已为空表!); return 0; return 1;/*输出元素*/int output_SeqList(SeqList *L) int i; for (i=0;ilast;i+) printf(%d ,L-datai); puts(); return(L-datai);void main() int s,x,y; SeqList L; init_SeqList(&L); printf(请输入顺序表长度: ); scanf(%d,&s); printf(请输入顺序表: ); input_SeqList(&L,s); /output_SeqList(&L); printf(输入x和y的值：); scanf(%d,%d,&x,&y); if (measure(&L,x,y,s) delete_list(&L,x,y); output_SeqList(&L); else printf(不存在xy之间的元素!);9 设A和B是两个按元素值递增有序的单链表，写一算法将A和B归并为按按元素值递减有序的单链表C，试分析算法的时间复杂度。答：node *mergelink(node *p, node *q) node *h, *r; h = (node*) malloc (sizeof(node); h-next = NULL; r = h; while (p != NULL & q != NULL) if (p-data data) r-next = p; r = p; p = p-nex