精華0
威望2
K幣268 元
注冊時間2016-11-14
在線時間0 小時
最后登錄2017-1-11
一般戰友
- 精華
- 0
- 威望
- 2
- K幣
- 268 元
- 注冊時間
- 2016-11-14
|
本帖最后由 失速的磚頭 于 2017-1-4 21:17 編輯
#include <stdio.h>
#include <stdlib.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef struct _SqList{
ElemType* elem;//elem指向數組的首地址
int length;//當前長度
int listsize;//數組的大小
}SqList;
Status InitList_Sq(SqList& L){
L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if (!L.elem){
printf("初始化失敗.\n");
return FALSE;
}
L.length = 0;
L.listsize = LIST_INIT_SIZE;
printf("初始化成功.\n");
return OK;
}
Status DestroyList_Sq(SqList& L){
//初始條件:線性表L存在
//操作結果:銷毀線性表L.
if (!L.elem){
printf("線性表不存在.\n");
return FALSE;
}
free(L.elem);
printf("線性表銷毀成功.\n");
return OK;
}
Status ClearList_Sq(SqList& L){
//初始條件:線性表L存在
//操作結果:將L重置為空表
if (!L.elem){
printf("線性表不存在.\n");
return FALSE;
}
InitList_Sq(L);
return OK;
}
Status ListEmpty_Sq(SqList L){
//初始條件:線性表L存在.
//操作結果:如果L是空表,返回TRUE,否則返回FALSE
if (L.length == 0){
printf("L是空表.\n");
return TRUE;
}
else{
printf("L不是空表.\n");
return FALSE;
}
}
Status ListLength_Sq(SqList L){
//初始條件:線性表L存在.
//操作結果:返回L中數據元素個數
return L.length;
}
Status GetElem_Sq(SqList L, int i, ElemType& e){
//初始條件:線性表已存在1 ≤ i ≤ ListLength(L).
//操作結果:用e返回L中第i個數據元素的值
e = L.elem[i-1];
return OK;
}
Status compare (ElemType x, ElemType y){
if (x == y){
return TRUE;
}
else{
return FALSE;
}
}
Status LocateElem_Sq(SqList L, ElemType e, Status(*compare) (ElemType, ElemType)){
//線性表L存在,compare()是數據元素判定函數.返回L中第1個與e滿足關系compare()的數據元素的位序.
//若這樣的元素不存在,則返回0;
int i = 1;//i的初值為第一個元素的位序
ElemType* p = L.elem;//p的初值為第一個元素的存儲位置(地址)
while (i <= L.length && !(*compare)(*p++, e))
++i;
if (i <= L.length)
return i;
else return FALSE;
}
int PriorElem_Sq(SqList L, ElemType cur_e, ElemType& pre_e){
//初始條件: 線性表L存在.
//操作結果: 若cur_e是L的數據元素,且不是第一個,則用pre_e返回他的前驅,否則操作失敗,pre_e無定義NULL.
int i = 1;
i = LocateElem_Sq(L, cur_e, compare);
if (i >1 && i <= L.length){ //符合條件
pre_e = L.elem[i-2];//減1是當前值,再減1是前驅值
}
else{
pre_e = 0;
return FALSE;
}
return OK;
}
Status NextElem_Sq(SqList L, ElemType cur_e, ElemType& next_e){
//初始條件: 線性表L存在.
//操作結果: 若cur_e是L的數據元素,且不是最后一個,則用next_e返回他的后繼,否則操作失敗,next_e無定義NULL.
int i = 1;
i = LocateElem_Sq(L, cur_e, compare);
if (i >=1 && i < L.length){ //符合條件
next_e = L.elem;//i在數組中就是他的后繼.
}
else{
next_e = 0;
return FALSE;
}
return OK;
}
Status ListInsert_Sq(SqList& L, int i, ElemType e){
//初始條件:線性表L存在,1 ≤ i ≤ ListLength(L)+1
//操作結果:在L中第i個位置之前插入新的數據元素e,L的長度加1
if (i<1 || i>L.length + 1)
return ERROR;
if (L.length >= L.listsize){
ElemType* newbase = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT)*sizeof(ElemType));
if (!newbase)
exit(OVERFLOW);
L.elem = newbase;
L.listsize += LISTINCREMENT;
}
ElemType* q = &(L.elem[i - 1]);
ElemType*p = NULL;
for (p = &(L.elem[L.length - 1]); p >= q; --p)
*(p + 1) = *p;
*q = e;
++L.length;
return OK;
}
Status ListDelete_Sq(SqList& L, int i, ElemType& e){
//初始條件:線性表L存在且非空,1 ≤ i ≤ ListLength(L)
//操作結果:刪除L的第i個數據元素,并用e返回其值,L的長度減1
if ((i<1) || (i > L.length))
return ERROR;
ElemType* p = NULL;
p = &(L.elem[i - 1]);
e = *p;
ElemType* q = NULL;
q = L.elem + L.length - 1;
for (++p; p <= q; ++p)
*(p - 1) = *p;
--L.length;
return OK;
}
ElemType& visit(ElemType& e){
//輸出線性表L一個數據元素.
return e;
}
Status ListTraverse_Sq(SqList L, ElemType& (*visit)(ElemType& e)){
//初始條件:線性表L存在
//操作結果:依次對L的每個數據元素調用函數visit().一旦visit()失敗,則操作失敗.
//就是遍歷函數
int i = 1;
ElemType p;
while (i<=L.length){
p = visit(*(L.elem++));
printf("%d ", p);
i++;
}
printf("\n");
return OK;
}
int main(void)
{
SqList p;
p.elem = NULL;
p.length = -1;
p.listsize = -1;
InitList_Sq(p);
DestroyList_Sq(p);
ClearList_Sq(p);
ListEmpty_Sq(p);
ListLength_Sq(p);
//插入線性表,
int e;
printf("在\"=\"后鍵入Ctrl+z表示輸入結束.\n");
while (1){
printf("請輸入第%d個元素的值=", ListLength_Sq(p)+1);
if (scanf("%d", &e) == EOF)
break;
ListInsert_Sq(p, ListLength_Sq(p) + 1, e);
}
ListTraverse_Sq(p, (*visit));
printf("--------------\n");
// 顯示長度
ListLength_Sq(p);
printf("數據元素的個數=%d\n",ListLength_Sq(p));
// 返回元素
int i = 1;//初始化i=1
printf("要返回第幾個元素的值(1 ≤ i ≤ %d) ", ListLength_Sq(p));
scanf("%d",&i);
GetElem_Sq(p, i, e);
printf("e=%d\n", e);
printf("--------------\n");
//判定函數
printf("請輸入要查找的數=", e);
scanf("%d", &e);
printf("在線性表(順序表)的第%d位\n", LocateElem_Sq(p, e, (*compare)));
printf("--------------\n");
//返回前驅的值
printf("請輸入要查找的數=", e);
int pre_e1 = 0;
scanf("%d", &e);
PriorElem_Sq(p, e, pre_e1);
printf("%d的前驅是=%d\n",e,pre_e1);
printf("--------------\n");
//返回后繼的值
printf("請輸入要查找的數=", e);
int next_e1 = 0;
scanf("%d", &e);
NextElem_Sq(p, e, next_e1);
printf("%d的后繼是=%d\n",e,next_e1);
printf("--------------\n");
// 插入函數
printf("請輸入要插入的位置(1≤i≤%d)=",ListLength_Sq(p)+1);
scanf("%d",&i);
printf("請輸入要插入的值=");
scanf("%d",&e);
ListInsert_Sq(p, i, e);
ListTraverse_Sq(p, (*visit));
printf("--------------\n");
//刪除函數
printf("請輸入要刪除的位置(1≤i≤%d)=",ListLength_Sq(p));
scanf("%d",&i);
ElemType del_e;
ListDelete_Sq(p, i, del_e);
ListTraverse_Sq(p, (*visit));
printf("--------------\n");
//再掉一次遍歷函數.
ListTraverse_Sq(p, (*visit));
return OK;
}
|
|
發表于 2017-1-4 21:10
收藏
分享
支持
反對
