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

《数据结构》课程设计报告
一、课程设计的内容、要求
1 线性表的另一种实现. 对顺序表空间被耗尽问题的一个解决办法是：当数组溢出时，用一个更大的数组替换该数组。一个较好的法则是：当出现溢出时，数组长度加长一倍具有较高的时间和空间效率。参照教材中顺序表的有关内容,按上面的要求实现顺序表，并测试当数组溢出时你的实现的运作情况。
二、所采用的数据结构
ADT List
｛
数据对象： D = {ai|ai ∈ElemSet， i=1，2…n>=0｝
数据关系: R1=｛〈ai-1, ai>｜ai-1， ai∈D, 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 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)；
}
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；
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〈〈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;
}
if(idx〉list—>size)
{
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；i<list—>size;i++）
{
cout<〈list—〉data［i]〈<” ";
｝
cout〈〈endl;
}
｝
void ClearList(LIST *list)
｛
list—〉size = 0；
free(list—〉data)；
InitList(list）；
cout〈〈"线性表已清空，当前元素个数为"〈〈list->size<<",线性表容量为”〈〈list—>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〈<endl；
}
｝
Print_list(&list)；
while（1）
｛
cout〈<"输入0 清空线性表，输入1指定位置插入元素，输入2指定位置删除元素，输入3退出:”<<endl；
fflush（stdin）;
cin>>i;
if（i == 0）
｛
ClearList（&list）;
｝
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〈<"警告：输入的位置大于元素的个数，将插入到末端.”〈<endl；
}
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<<”您的输入有误,请重新输入:”〈<endl;
}
cout〈<”请输入要删除元素的位置：";
fflush（stdin）;
}
while（！（(cin〉〉i）。good()））；
int e;
if(i>list。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，线性表的容量为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退出:
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 页