#include <stdio.h>
#include <stdlib.h>
typedef int elemType;
/************************************************************************/
/* 以下是關于線性表順序存儲操作的16種算法 */
/************************************************************************/
strUCt List{
elemType *list;
int size;
int maxSize;
};
void againMalloc(struct List *L)
{
/* 空間擴展為原來的2倍，并由p指針所指向，原內容被自動拷貝到p所指向的存儲空間 */
elemType *p = realloc(L->list, 2 * L->maxSize * sizeof(elemType));
if(!p){ /* 分配失敗則退出運行 */
exit(1);
}
L->list = p; /* 使list指向新線性表空間 */
L->maxSize = 2 * L->maxSize; /* 把線性表空間大小修改為新的長度 */
}
/* 1.初始化線性表L，即進行動態存儲空間分配并置L為一個空表 */
void initList(struct List *L, int ms)
{
/* 檢查ms是否有效，若無效的則退出運行 */
if(ms <= 0){
printf("MaxSize非法！ ");
exit(1); /* 執行此函數中止程序運行，此函數在stdlib.h中有定義 */
}
L->maxSize = ms; /* 設置線性表空間大小為ms */
L->size = 0;
L->list = malloc(ms * sizeof(elemType));
if(!L->list){
printf("空間分配失??！ ");
exit(1);
}
return;
}
/* 2.清除線性表L中的所有元素，釋放存儲空間，使之成為一個空表 */
void clearList(struct List *L)
{
if(L->list != NULL){
free(L->list);
L->list = 0;
L->size = L->maxSize = 0;
}
return;
}
/* 3.返回線性表L當前的長度，若L為空則返回０ */
int sizeList(struct List *L)
{
return L->size;
}
/* 4.判定線性表L是否為空，若為空則返回1, 否則返回0 */
int emptyList(struct List *L)
{
if(L->size ==0){
return 1;
}
else{
return 0;
}
}
/* 5.返回線性表L中第pos個元素的值，若pos超出范圍，則停止程序運行 */
elemType getElem(struct List *L, int pos)
{
if(pos < 1 pos > L->size){ /* 若pos越界則退出運行 */
printf("元素序號越界！ ");
exit(1);
}
return L->list[pos - 1]; /* 返回線性表中序號為pos值的元素值 */
}
/* 6.順序掃描（即遍歷）輸出線性表L中的每個元素 */
void traverseList(struct List *L)
{
int i;
for(i = 0; i < L->size; i++){
printf("%d ", L ->list[i]);
}
printf(" ");
return;
}
/* 7.從線性表L中查找值與x相等的元素，若查找成功則返回其位置，否則返回-1 */
int findList(struct List *L, elemType x)
{
int i;
for(i = 0; i < L->size; i++){
if(L->list[i] == x){
return i;
}
}
return -1;
}
/* 8.把線性表L中第pos個元素的值修改為x的值，若修改成功返回1，否則返回0 */
int updatePosList(struct List *L, int pos, elemType x)
{
if(pos < 1 pos > L->size){ /* 若pos越界則修改失敗 */
return 0;
}
L->list[pos - 1] = x;
return 1;
}
/* 9.向線性表L的表頭插入元素x */
void inserFirstList(struct List *L, elemType x)
{
int i;
if(L->size == L->maxSize){
againMalloc(L);
}
for(i = L->size - 1; i >= 0; i--){
L->list[i + 1] = L ->list[i];
}
L->list[0] = x;
L->size ++;
return;
}
/* 10.向線性表L的表尾插入元素x */
void insertLastList(struct List *L, elemType x)
{
if(L->size == L ->maxSize){ /* 重新分配更大的存儲空間 */
againMalloc(L);
}
L->list[L->size] = x; /* 把x插入到表尾 */
L->size++; /* 線性表的長度增加１ */
return;
}
/* 11.向線性表L中第pos個元素位置插入元素x，若插入成功返回１，否則返回０ */
int insertPosList(struct List *L, int pos, elemType x)
{
int i;
if(pos < 1 pos > L->size + 1){ /* 若pos越界則插入失敗 */
return 0;
}
if(L->size == L->maxSize){ /* 重新分配更大的存儲空間 */
againMalloc(L);
}
for(i = L->size - 1; i >= pos - 1; i--){
L->list[i + 1] = L->list[i];
}
L->list[pos - 1] = x;
L->size++;
return 1;
}
/* 12.向有序線性表L中插入元素x, 使得插入后仍然有序*/
void insertOrderList(struct List *L, elemType x)
{
int i, j;
/* 若數組空間用完則重新分配更大的存儲空間 */
if(L->size == L->maxSize){
againMalloc(L);
}
/* 順序查找出x的插入位置 */
for(i = 0; i < L->size; i++){
if(x < L->list[i]){
break;
}
}
/* 從表尾到下標i元素依次后移一個位置， 把i的位置空出來 */
for(j = L->size - 1; j >= i; j--)
L->list[j+1] = L->list[j];
/* 把x值賦給下標為i的元素 */
L->list[i] = x;
/* 線性表長度增加1 */
L->size++;
return;
}
/* 13.從線性表L中刪除表頭元素并返回它，若刪除失敗則停止程序運行 */
elemType deleteFirstList(struct List *L)
{
elemType temp;
int i;
if(L ->size == 0){
printf("線性表為空，不能進行刪除操作！ ");
exit(1);
}
temp = L->list[0];
for(i = 1; i < L->size; i++)
L->list[i-1] = L->list[i];
L->size--;
return temp;
}
/* 14.從線性表L中刪除表尾元素并返回它，若刪除失敗則停止程序運行 */
elemType deleteLastList(struct List *L)
{
if(L ->size == 0){
printf("線性表為空，不能進行刪除操作！ ");
exit(1);
}
L->size--;
return L ->list[L->size]; /* 返回原來表尾元素的值 */
}
/* 15.從線性表L中刪除第pos個元素并返回它，若刪除失敗則停止程序運行 */
elemType deletePosList(struct List *L, int pos)
{
elemType temp;
int i;
if(pos < 1 pos > L->size){ /* pos越界則刪除失敗 */
printf("pos值越界，不能進行刪除操作！ ");
exit(1);
}
temp = L->list[pos-1];
for(i = pos; i < L->size; i++)
L->list[i-1] = L->list[i];
L->size--;
return temp;
}
/* 16.從線性表L中刪除值為x的第一個元素，若成功返回1，失敗返回0 */
int deleteValueList(struct List *L, elemType x)
{
int i, j;
/* 從線性表中順序查找出值為x的第一個元素 */
for(i = 0; i < L->size; i++){
if(L->list[i] == x){
break;
}
}
/* 若查找失敗，表明不存在值為x的元素，返回0 */
if(i == L->size){
return 0;
}
/* 刪除值為x的元素L->list[i] */
for(j = i + 1; j < L->size; j++){
L->list[j-1] = L->list[j];
}
L->size--;
return 1;
}
/************************************************************************/
void main()
{
int a[10] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
int i;
struct List L;
initList(&L, 5);
for(i = 0; i < 10; i++){
insertLastList(&L, a[i]);
}
insertPosList(&L, 11, 48); insertPosList(&L, 1, 64);
printf("%d ", getElem(&L, 1));
traverseList(&L);
printf("%d ", findList(&L, 10));
updatePosList(&L, 3, 20);
printf("%d ", getElem(&L, 3));
traverseList(&L);
deleteFirstList(&L); deleteFirstList(&L);
deleteLastList(&L); deleteLastList(&L);
deletePosList(&L, 5); ;deletePosList(&L, 7);
printf("%d ", sizeList(&L));
printf("%d ", emptyList(&L));
traverseList(&L);
clearList(&L);
return 0;
}
更多內容請看C/C++進階技術文檔 數據結構 數據結構相關文章專題，或 
