线性表的另一种实现--数据结构课程设计报告.doc

数据结构课程设计报告一、课程设计的内容、要求1 线性表的另一种实现. 对顺序表空间被耗尽问题的一个解决办法是：当数组溢出时，用一个更大的数组替换该数组。一个较好的法则是：当出现溢出时，数组长度加长一倍具有较高的时间和空间效率。参照教材中顺序表的有关内容,按上面的要求实现顺序表，并测试当数组溢出时你的实现的运作情况。二、所采用的数据结构ADT List数据对象： D = ai|ai ElemSet， i=1，2n=0数据关系: R1=ai-1, aiai-1， aiD, i=1，2，n基本操作:void IniList（SqList& L);void DestroyList(SqList& L);bool ListEmpty（SqList L);int ListLength(SqList L）;void GetElem（SqList L, int i, Elem e)；bool PriorElem（SqList L， Elem cur_e, Elem &pre_e）;bool NextElem(SqList L， Elem cur_e, Elem next_e)；void ListInsert（SqList &L， int i， Elem e)；void ListDelete（SqList &L， int i);void ClearList（SqList& L);三、主要模块(或函数)及其功能typedef struct LISTElemType *data；int size;int max_size； LIST；void InitList(LIST list）/初始化listdata = （int)malloc（sizeof（ElemType）*INIT_SIZE）；listsize = 0；list-max_size = INIT_SIZE；void DestroyList(LIST &list）list.size = 0； list。max_size = 0;free(list.data)；bool ListEmpty（LIST list）if(list。size 0） return false；else return true;int ListLength(LIST list)return list.size；bool GetElem（LIST list，int i，ElemType &e)if（i list。size） return false;elsee = list。datai；return true;int LocateElem（LIST list， ElemType e，bool (*compare)（ElemType, ElemType) / 在顺序线性表L中查找第1个值与e满足compare()的元素的位序./ 若找到，则返回其在L中的位序，否则返回0。int i；ElemType *p；i = 0； p = list。data； while (i = list.size & !(*compare）（p+， e)） +i；if (i = list。size） return i;else return 0； bool PriorElem(LIST list,int cur_e，int pre_e)/前驱if(cur_e 0 | cur_e list.size ) return false；else pre_e = cur_e - 1;return true;bool NextElem(LIST list，int cur_e,int &next_e)/后继if(cur_e list。size) return false；else next_e = cur_e + 1;return true;void Insert（LIST list,ElemType value）if(listsize=listmax_size）int i;ElemType temp = （int*)malloc(sizeof（ElemType)listsize2)；coutendlsize；i+）tempi = list-datai；free(listdata);list-data = temp；list-max_size*=2；cout改变后大小max_sizesize+；void Insert_Back（LIST list,int idx,ElemType value)if(list-size=list-max_size）int i；ElemType temp = (int*）malloc(sizeof（ElemType)*list-size*2）;coutendl”线性表原容量改变:原大小为”size;i+）tempi = listdatai；free(list-data);listdata = temp；listmax_size=2；cout”改变后大小”size)listdatalist-size = value;elseint i；for(i=listsize;iidx;i-）listdatai = listdatai-1;listdataidx = value;listsize+;void ListDelete(LIST list，int i，ElemType *e)/删除一个元素int j;e=listdatai；for（j=i+1；j=list-size1;j+）listdataj-1=list-dataj;listsize-；void Print_list（LIST *list)int i；if（listsize = 0)cout当前线性表内没有元素。endl；elsecout”线性表内的元素有：”;for（i=0；isize;i+）coutlistdataisizemax_sizeendl；四、主要模块（或函数）的算法思想和程序框图int i;LIST list;InitList（list）；while(1）coutn）。good()cin.clear（）;char ch;cinch;if（ch=#）break；elsecout您的输入有误，请重新输入endl;continue;elseInsert(&list,n）;cout当前线性表的元素个数为list.size”,线性表的容量为list.max_sizeendl；Print_list(&list)；while（1）cout输入0 清空线性表，输入1指定位置插入元素，输入2指定位置删除元素，输入3退出:”i;if（i = 0）ClearList（&list）;else if（i = 1)int idx;doif(！cin.good（)）cin.clear（)；cout您的输入有误，请重新输入:endl；coutidx）.good（）)）；int n；if(idxlist。size)cout警告：输入的位置大于元素的个数，将插入到末端.”endl；doif(!cin。good（）)cin.clear()；cout您的输入有误，请重新输入:”n）。good（）)）;Insert_Back（&list，idx,n);Print_list（&list）;else if(i =2)int i；doif（!cin.good（)cin。clear();cout”您的输入有误,请重新输入:”endl;coutlist。size）cout”警告：删除的位置大于元素的个数，删除无效。endl;continue;ListDelete（list,i，e）;Print_list（&list）；else if(i = 3）break；else if（i 3)cout您的输入有误,请重新输入:endl；continue；五、程序运行时的输入数据（随机产生的数据要求输出显示），输出结果循环输入整数元素(输入结束）:1当前线性表的元素个数为1，线性表的容量为22当前线性表的元素个数为2,线性表的容量为23线性表原容量改变：原大小为2改变后大小4当前线性表的元素个数为3，线性表的容量为4线性表内的元素有:1 2 3输入0 清空线性表，输入1指定位置插入元素，输入2指定位置删除元素，输入3退出：1请输入要插入元素的位置:0请输入要插入整数的值：5线性表内的元素有：5 1 2 3输入0 清空线性表,输入1指定位置插入元素，输入2指定位置删除元素，输入3退出:1请输入要插入元素的位置：6警告：输入的位置大于元素的个数，将插入到末端.请输入要插入整数的值：10线性表原容量改变：原大小为4改变后大小8线性表内的元素有：5 1 2 3 10输入0 清空线性表，输入1指定位置插入元素，输入2指定位置删除元素,输入3退出：2请输入要删除元素的位置：0线性表内的元素有：1 2 3 10输入0 清空线性表，输入1指定位置插入元素，输入2指定位置删除元素，输入3退出：3循环输入整数元素（输入结束)：线性表内的元素有：1 2 3 10输入0 清空线性表，输入1指定位置插入元素,输入2指定位置删除元素,输入3退出:第 8 页 共 8 页