《数据结构》课程设计报告范本(doc 8页).doc

数据结构课程设计报告一、课程设计的内容、要求1 线性表的另一种实现。 对顺序表空间被耗尽问题的一个解决办法是：当数组溢出时，用一个更大的数组替换该数组。一个较好的法则是：当出现溢出时，数组长度加长一倍具有较高的时间和空间效率。参照教材中顺序表的有关内容，按上面的要求实现顺序表，并测试当数组溢出时你的实现的运作情况。二、所采用的数据结构ADT List数据对象: D = ai|ai ElemSet, i=1,2n=0数据关系: R1=|ai-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)/初始化list-data = (int*)malloc(sizeof(ElemType)*INIT_SIZE);list-size = 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 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(list-size=list-max_size)int i;ElemType *temp = (int*)malloc(sizeof(ElemType)*list-size*2);coutendl线性表原容量改变：原大小为max_size;for(i=0;isize;i+)tempi = list-datai;free(list-data);list-data = temp;list-max_size*=2;cout改变后大小max_sizedatalist-size = value;list-size+;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线性表原容量改变：原大小为max_size;for(i=0;isize;i+)tempi = list-datai;free(list-data);list-data = temp;list-max_size*=2;cout改变后大小max_sizelist-size)list-datalist-size = value;elseint i;for(i=list-size;iidx;i-)list-datai = list-datai-1;list-dataidx = value;list-size+;void ListDelete(LIST *list,int i,ElemType *e)/删除一个元素int j;*e=list-datai;for(j=i+1;jsize-1;j+)list-dataj-1=list-dataj;list-size-;void Print_list(LIST *list)int i;if(list-size = 0)cout当前线性表内没有元素。endl;elsecout线性表内的元素有：;for(i=0;isize;i+)coutdatai ;coutsize = 0;free(list-data);InitList(list);cout线性表已清空，当前元素个数为size，线性表容量为max_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您的输入有误,请重新输入:endl;coutn).good();Insert_Back(&list,idx,n);Print_list(&list);else if(i =2)int i;doif(!cin.good()cin.clear();cout您的输入有误,请重新输入:endl;couti).good();int e;if(ilist.size)cout警告：删除的位置大于元素的个数,删除无效。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