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

一、课程设计的内容、要求

1 线性表的另一种实现。 对顺序表空间被耗尽问题的一个解决办法是:当数组溢出时，用一个更大的数组替换该数组.一个较好的法则是：当出现溢出时，数组长度加长一倍具有较高的时间和空间效率。参照教材中顺序表的有关内容，按上面的要求实现顺序表，并测试当数组溢出时你的实现的运作情况。 二、所采用的数据结构 ADT List {

数据对象： D = ｛ai｜ai ∈ElemSet, i=1,2…n>=0｝ 数据关系: R1={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 LIST ｛

ElemType ＊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）； }

第 1 页 共 8 页

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 〈 1 ｜| i > list。size） return false； else ｛

e = list。data[i]; 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 < 0 |｜ cur_e > list.size) return false；

第 2 页 共 8 页

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）; cout<〈endl<<\"线性表原容量改变:原大小为”<〈list->max_size； for(i=0;i〈list—>size;i++) {

temp[i］ = list-〉data［i］; ｝

free(list-〉data); list->data = temp; list->max_size＊=2; cout〈<\"改变后大小\"〈〈list->max_size<〈endl; }

list—>data［list-〉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);

cout〈max_size; for（i=0;i〈list—>size；i++) ｛

temp［i] = list—>data［i］； ｝

free(list—>data)； list-〉data = temp； list->max_size*=2； cout〈〈”改变后大小\"<if(idx〉list—>size） {

第 3 页 共 8 页

list—〉data［list->size] = value； } else ｛

int i；

for（i=list—>size；i>idx；i—-） {

list->data[i] = list—>data[i—1］； ｝

list—>data[idx] = value； ｝

list—〉size++; ｝

void ListDelete（LIST ＊list,int i,ElemType *e)//删除一个元素 ｛

int j；

＊e=list-〉data［i］；

for（j=i+1；j<=list—>size-1;j++） list->data［j—1]=list—>data[j］； list->size--; ｝

void Print_list（LIST *list) ｛

int i;

if（list->size == 0） ｛

cout〈〈”当前线性表内没有元素。\"〈〈endl； ｝ else ｛

cout<〈”线性表内的元素有：”； for(i=0;isize；i++） {

cout〈data[i］〈<” ”; }

cout〈void ClearList（LIST *list） ｛

list—〉size = 0； free（list—>data）； InitList(list）； cout〈〈\"线性表已清空，当前元素个数为”〈〈list—>size<〈”，线性表容

第 4 页 共 8 页

量为”<max_size<〈endl； }

四、主要模块（或函数）的算法思想和程序框图 int i；

LIST list;

InitList（&list); while（1) ｛

cout〈〈\"循环输入整数元素（输入#结束）:”； while(1） {

int n;

fflush(stdin)；//清空输入缓冲区，避免缓冲区内残存读取函数无法取走的内容 if（！（(cin〉>n)。good（））） ｛

cin.clear（）； char ch;

cin〉>ch; if(ch==’＃') break； else {

cout<〈\"您的输入有误,请重新输入”〈〈endl; continue; } } else ｛

Insert（&list,n）；

cout〈<\"当前线性表的元素个数为\"〈〈list.size〈<\"，线性表的容量为\"〈〈list.max_size〈Print_list（&list）; while(1） ｛

cout<<\"输入0 清空线性表，输入1指定位置插入元素,输入2指定位置删除元素,输入3退出：”<〈endl； fflush(stdin）； cin>〉i; if（i == 0） ｛

ClearList（&list)；

第 5 页 共 8 页

｝

else if（i == 1) ｛

int idx; do ｛

<if（！cin。good（)） ｛

cin。clear(）； cout〈〈”您的输入有误,请重新输入：\"<〈endl; }

cout〈<”请输入要插入元素的位置：\"； fflush(stdin）; }

while(！（(cin>>idx）。good()）)； int n;

if(idx〉list.size） ｛

cout〈<”警告:输入的位置大于元素的个数，将插入到末端.” } do {

if(!cin.good（)） ｛

cin.clear(）;

cout<〈”您的输入有误,请重新输入：\"〈〈endl; ｝

cout<<”请输入要插入整数的值:\"； fflush（stdin）； ｝

while（！(（cin〉〉n）.good（））)； Insert_Back(&list，idx，n); Print_list（&list); }

else if（i ==2) ｛

int i; do {

if(!cin.good(）) {

cin。clear();

cout〈<”您的输入有误,请重新输入：\"<第 6 页 共 8 页

｝ cout〈〈”请输入要删除元素的位置：\"； fflush(stdin)； }

while（！（(cin〉>i).good（))）； int e;

if(i>list.size） ｛

cout〈<\"警告：删除的位置大于元素的个数,删除无效。\"<continue; ｝

ListDelete(&list,i,&e)； Print_list(＆list）； ｝

else if（i == 3） {

break; ｝

else if（i >3） ｛

cout<〈”您的输入有误，请重新输入：\"<五、程序运行时的输入数据（随机产生的数据要求输出显示)，输出结果 循环输入整数元素(输入＃结束）:1

当前线性表的元素个数为1,线性表的容量为2 2

当前线性表的元素个数为2，线性表的容量为2 3

线性表原容量改变:原大小为2改变后大小4 当前线性表的元素个数为3,线性表的容量为4 #

线性表内的元素有：1 2 3

输入0 清空线性表,输入1指定位置插入元素，输入2指定位置删除元素，输入3退出: 1

请输入要插入元素的位置：0 请输入要插入整数的值:5 线性表内的元素有:5 1 2 3

输入0 清空线性表,输入1指定位置插入元素，输入2指定位置删除元素,输入3退出：

第 7 页 共 8 页

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 页