程序師世界是廣大編程愛好者互助、分享、學習的平台，程序師世界有你更精彩！
設為首頁 加入收藏
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 線性表的順序表示和實現

線性表的順序表示和實現

編輯：C++入門知識

線性表的順序表示和實現

Common.h


[cpp]
#define TRUE        1  
#define FALSE       0  
#define OK          1  
#define ERROR       0  
#define INFEASIBLE  -1  
#define OVERFLOW    -2  
 
typedef int Status; 

#define TRUE     1
#define FALSE  0
#define OK   1
#define ERROR  0
#define INFEASIBLE  -1
#define OVERFLOW -2

typedef int Status;
SqList.h


[cpp]
//------線性表的動態分配順序存儲結構--------  
 
 
#include <stdlib.h>  
#include "Common.h"  
 
#define ElemType int  
 
#define LIST_INIT_SIZE  100 //線性表存儲空間的初始分配量  
#define LISTINCREMENT   10  //線性表存儲空間的分配增量  
 
typedef struct{ 
    ElemType* elem; //存儲空間基址  
    int length;         //當前長度  
    int listsize;       //當前分配的存儲容量（以sizeof(ElemType)為單位）  
} SqList; 
 
//基本操作  
 
Status InitList(SqList &L); 
    //操作結果：構造一個空的線性表L。  
 
Status DestroyList(SqList &L); 
    //初始條件：線性表L已存在。  
    //操作結果：銷毀線性表L。  
 
Status ClearList(SqList &L); 
    //初始條件：線性表L已存在。  
    //操作結果：將L重置為空表。  
 
bool ListEmpty(SqList L); 
    //初始條件：線性表L已存在。  
    //操作結果：若L為空表，則返回TRUE，否則返回FALSE。  
 
int ListLength(SqList L); 
    //初始條件：線性表L已存在。  
    //操作結果：返回L中數據元素的個數。  
 
Status GetElem(SqList L, int i, ElemType &e); 
    //初始條件：線性表L已存在，1<=i<=ListLength(L)。  
    //操作結果：用e返回L中第i個數據元素的值。  
 
int LocateElem(SqList L, int e, bool (*equal)(ElemType, ElemType)); 
    //初始條件：線性表L已存在，compare()是數據元素判定函數。  
    //返回L中第一個與e滿足關系compare()的數據元素的位序。若這樣的數據元素不存在，則返回值為0.  
 
Status PriorElem(SqList L, ElemType cur_e, ElemType &pre_e); 
    //初始條件：線性表L已存在。  
    //操作結果：若cur_e是L中的數據元素，且不是第一個，則用pre_e返回它的前驅，否則操作失敗，pre_e無定義。  
 
Status NextElem(SqList L, ElemType cur_e, ElemType &next_e); 
    //初始條件：線性表L已存在。  
    //操作結果：若cur_e是L中的數據元素，且不是最後一個，則用next_e返回它的後繼，否則操作失敗，next_e無定義。  
 
Status ListInsert(SqList &L, int i, ElemType e); 
    //初始條件：線性表L已存在，1<=i<=ListLength(L)+1.  
    //操作結果：在L中第i個位置之前插入新的數據元素e，L的長度加1.  
 
Status ListDelete(SqList &L, int i, ElemType &e); 
    //初始條件：線性表L已存在且非空，1<=i<=ListLength(L).  
    //操作結果：刪除L的第i個數據元素，並用e返回其值，L的長度減1.  
 
Status ListTraverse(SqList L, bool (*visit)(ElemType)); 
    //初始條件：線性表L已存在  
    //操作結果：依次對L的每個元素調用函數visit().一旦visit()失敗,則操作失敗。  
     

//------線性表的動態分配順序存儲結構--------


#include <stdlib.h>
#include "Common.h"

#define ElemType int

#define LIST_INIT_SIZE 100 //線性表存儲空間的初始分配量
#define LISTINCREMENT 10 //線性表存儲空間的分配增量

typedef struct{
 ElemType* elem; //存儲空間基址
 int length;   //當前長度
 int listsize;  //當前分配的存儲容量（以sizeof(ElemType)為單位）
} SqList;

//基本操作

Status InitList(SqList &L);
 //操作結果：構造一個空的線性表L。

Status DestroyList(SqList &L);
 //初始條件：線性表L已存在。
 //操作結果：銷毀線性表L。

Status ClearList(SqList &L);
 //初始條件：線性表L已存在。
 //操作結果：將L重置為空表。

bool ListEmpty(SqList L);
 //初始條件：線性表L已存在。
 //操作結果：若L為空表，則返回TRUE，否則返回FALSE。

int ListLength(SqList L);
 //初始條件：線性表L已存在。
 //操作結果：返回L中數據元素的個數。

Status GetElem(SqList L, int i, ElemType &e);
 //初始條件：線性表L已存在，1<=i<=ListLength(L)。
 //操作結果：用e返回L中第i個數據元素的值。

int LocateElem(SqList L, int e, bool (*equal)(ElemType, ElemType));
 //初始條件：線性表L已存在，compare()是數據元素判定函數。
 //返回L中第一個與e滿足關系compare()的數據元素的位序。若這樣的數據元素不存在，則返回值為0.

Status PriorElem(SqList L, ElemType cur_e, ElemType &pre_e);
 //初始條件：線性表L已存在。
 //操作結果：若cur_e是L中的數據元素，且不是第一個，則用pre_e返回它的前驅，否則操作失敗，pre_e無定義。

Status NextElem(SqList L, ElemType cur_e, ElemType &next_e);
 //初始條件：線性表L已存在。
 //操作結果：若cur_e是L中的數據元素，且不是最後一個，則用next_e返回它的後繼，否則操作失敗，next_e無定義。

Status ListInsert(SqList &L, int i, ElemType e);
 //初始條件：線性表L已存在，1<=i<=ListLength(L)+1.
 //操作結果：在L中第i個位置之前插入新的數據元素e，L的長度加1.

Status ListDelete(SqList &L, int i, ElemType &e);
 //初始條件：線性表L已存在且非空，1<=i<=ListLength(L).
 //操作結果：刪除L的第i個數據元素，並用e返回其值，L的長度減1.

Status ListTraverse(SqList L, bool (*visit)(ElemType));
 //初始條件：線性表L已存在
 //操作結果：依次對L的每個元素調用函數visit().一旦visit()失敗,則操作失敗。
 
SqList.cpp


[cpp]
#include <malloc.h>  
#include "SqList.h"  
 
Status InitList(SqList &L){ 
    //操作結果：構造一個空的線性表L。  
 
    L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)); 
    if(!L.elem) exit(OVERFLOW); //存儲分配失敗  
    L.length = 0; 
    L.listsize = LIST_INIT_SIZE; 
    return OK; 
}//InitList  
 
Status DestroyList(SqList &L){ 
    //操作結果：銷毀線性表L。  
 
    free(&L); 
     
    return OK; 
} 
 
Status ClearList(SqList &L) { 
    //操作結果：將L重置為空表。  
    L.length = 0; 
    return OK; 
} 
 
bool ListEmpty(SqList L){ 
    //操作結果：若L為空表，則返回TRUE，否則返回FALSE。  
 
    if(0 == L.length) 
        return true; 
    else return false; 
} 
 
int ListLength(SqList L){ 
    //操作結果：返回L中數據元素的個數。  
 
    return L.length; 
} 
 
Status GetElem(SqList L, int i, ElemType &e){ 
    //1<=i<=ListLength(L)。  
    //操作結果：用e返回L中第i個數據元素的值。  
 
    if(i < 1  ||  i>=L.length) return ERROR; 
    e = L.elem[i-1]; 
    return OK; 
} 
 
int LocateElem(SqList L, ElemType e, bool (*equal)(ElemType, ElemType)){ 
    //compare()是數據元素判定函數。  
    //返回L中第一個與e滿足關系compare()的數據元素的位序。若這樣的數據元素不存在，則返回值為0.  
 
    int i = 1; 
    ElemType* p = L.elem; 
    while(i <= L.length  &&  !(*equal)(*p++, e)) ++i; 
    if(i <= L.length) return i; 
    else return 0; 
} 
 
Status PriorElem(SqList L, ElemType cur_e, ElemType &pre_e){ 
    //操作結果：若cur_e是L中的數據元素，且不是第一個，則用pre_e返回它的前驅，否則操作失敗，pre_e無定義。  
         
        int i=1; 
        while(i <= L.length  && !(cur_e==L.elem[i-1])) ++i; 
        if(i<2 || i>L.length) 
            return ERROR; 
        pre_e = L.elem[i-2]; 
        return OK; 
} 
 
Status NextElem(SqList L, ElemType cur_e, ElemType &next_e){ 
    //操作結果：若cur_e是L中的數據元素，且不是最後一個，則用next_e返回它的後繼，否則操作失敗，next_e無定義。  
 
        int i=1; 
        while(i <= L.length  && !(cur_e==L.elem[i-1])) ++i; 
        if(i<2 || i>L.length) 
            return ERROR; 
        next_e = L.elem[i]; 
        return OK; 
} 
 
Status ListInsert(SqList &L, int i, ElemType e){ 
    //1<=i<=ListLength(L)+1.  
    //操作結果：在L中第i個位置之前插入新的數據元素e，L的長度加1.  
 
    if(i < 1 || i>L.length+1) return ERROR;   //i值不合法  
    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]);  //q為插入位置  
    ElemType * p; 
    for(p=&(L.elem[L.length-1]);p>=q;--p) 
        *(p+1) = *p;    //右移  
 
    *q = e; 
    ++L.length; 
    return OK; 
}//ListInsert  
 
Status ListDelete(SqList &L, int i, ElemType &e){ 
    //1<=i<=ListLength(L).  
    //操作結果：刪除L的第i個數據元素，並用e返回其值，L的長度減1.  
 
    if(i<1 || i>L.length) return ERROR; 
    ElemType* p = &(L.elem[i-1]); 
    e = *p; 
    ElemType* q = L.elem + L.length - 1; 
    for(++p;p<=q;++p) *(p-1) = *p; 
    --L.length; 
    return OK; 
} 
 
Status ListTraverse(SqList L, bool (*visit)(ElemType)){ 
    //操作結果：依次對L的每個元素調用函數visit().一旦visit()失敗,則操作失敗。  
 
    int i=1; 
    ElemType* p = L.elem; 
    while(i <= L.length  &&  (*visit)(*p++)) ++i;  
    return OK; 
} 

#include <malloc.h>
#include "SqList.h"

Status InitList(SqList &L){
 //操作結果：構造一個空的線性表L。

 L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
 if(!L.elem) exit(OVERFLOW); //存儲分配失敗
 L.length = 0;
 L.listsize = LIST_INIT_SIZE;
 return OK;
}//InitList

Status DestroyList(SqList &L){
 //操作結果：銷毀線性表L。

 free(&L);
 
 return OK;
}

Status ClearList(SqList &L) {
 //操作結果：將L重置為空表。
 L.length = 0;
 return OK;
}

bool ListEmpty(SqList L){
 //操作結果：若L為空表，則返回TRUE，否則返回FALSE。

 if(0 == L.length)
  return true;
 else return false;
}

int ListLength(SqList L){
 //操作結果：返回L中數據元素的個數。

 return L.length;
}

Status GetElem(SqList L, int i, ElemType &e){
 //1<=i<=ListLength(L)。
 //操作結果：用e返回L中第i個數據元素的值。

 if(i < 1  ||  i>=L.length) return ERROR;
 e = L.elem[i-1];
 return OK;
}

int LocateElem(SqList L, ElemType e, bool (*equal)(ElemType, ElemType)){
 //compare()是數據元素判定函數。
 //返回L中第一個與e滿足關系compare()的數據元素的位序。若這樣的數據元素不存在，則返回值為0.

 int i = 1;
 ElemType* p = L.elem;
 while(i <= L.length  &&  !(*equal)(*p++, e)) ++i;
 if(i <= L.length) return i;
 else return 0;
}

Status PriorElem(SqList L, ElemType cur_e, ElemType &pre_e){
 //操作結果：若cur_e是L中的數據元素，且不是第一個，則用pre_e返回它的前驅，否則操作失敗，pre_e無定義。
  
  int i=1;
  while(i <= L.length  && !(cur_e==L.elem[i-1])) ++i;
  if(i<2 || i>L.length)
   return ERROR;
  pre_e = L.elem[i-2];
  return OK;
}

Status NextElem(SqList L, ElemType cur_e, ElemType &next_e){
 //操作結果：若cur_e是L中的數據元素，且不是最後一個，則用next_e返回它的後繼，否則操作失敗，next_e無定義。

  int i=1;
  while(i <= L.length  && !(cur_e==L.elem[i-1])) ++i;
  if(i<2 || i>L.length)
   return ERROR;
  next_e = L.elem[i];
  return OK;
}

Status ListInsert(SqList &L, int i, ElemType e){
 //1<=i<=ListLength(L)+1.
 //操作結果：在L中第i個位置之前插入新的數據元素e，L的長度加1.

 if(i < 1 || i>L.length+1) return ERROR; //i值不合法
 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]); //q為插入位置
 ElemType * p;
 for(p=&(L.elem[L.length-1]);p>=q;--p)
  *(p+1) = *p; //右移

 *q = e;
 ++L.length;
 return OK;
}//ListInsert

Status ListDelete(SqList &L, int i, ElemType &e){
 //1<=i<=ListLength(L).
 //操作結果：刪除L的第i個數據元素，並用e返回其值，L的長度減1.

 if(i<1 || i>L.length) return ERROR;
 ElemType* p = &(L.elem[i-1]);
 e = *p;
 ElemType* q = L.elem + L.length - 1;
 for(++p;p<=q;++p) *(p-1) = *p;
 --L.length;
 return OK;
}

Status ListTraverse(SqList L, bool (*visit)(ElemType)){
 //操作結果：依次對L的每個元素調用函數visit().一旦visit()失敗,則操作失敗。

 int i=1;
 ElemType* p = L.elem;
 while(i <= L.length  &&  (*visit)(*p++)) ++i;
 return OK;
}
main.cpp


[cpp]
#include <stdio.h>  
#include "SqList.h"  
 
 
bool equal(int a, int b){ 
    if(a == b) 
        return true; 
    return false; 
} 
 
bool visit(ElemType e){ 
    printf(" %d", e); 
    return true; 
} 
 
int main() 
{ 
    SqList L; 
    ElemType e; 
    ElemType pre_e; 
    ElemType next_e; 
 
    InitList(L); 
    if(ListEmpty(L)) 
        printf("kong\n"); 
 
    for(int i=0;i<30;i++){ 
        e = i+1; 
        ListInsert(L, i+1, e); 
    } 
     
    e = 15; 
    printf("15所在的位置為： %d\n", LocateElem(L, 15, equal)); 
    PriorElem(L, e, pre_e); 
    NextElem(L, e, next_e); 
    printf("e的前驅為：%d\n", pre_e); 
    printf("e的後驅為：%d\n", next_e); 
 
    GetElem(L, 22, e); 
    printf("第22個數為：%d\n", e); 
     
    printf("遍歷："); 
    ListTraverse(L, visit); 
    printf("\n"); 
    printf("List length is：%d\n", ListLength(L)); 
    ClearList(L); 
    printf("清空\n"); 
    printf("List length is：%d\n", ListLength(L)); 
    if(ListEmpty(L)) 
        printf("kong\n"); 
 
    ListInsert(L, 1, 3); 
    ListInsert(L, 2, 7); 
    ListInsert(L, 3, 9); 
    ListInsert(L, 4, 1); 
    ListInsert(L, 5, 44); 
    printf("List length is：%d\n", ListLength(L)); 
    printf("遍歷："); 
    ListTraverse(L, visit); 
    printf("\n"); 
 
    ListDelete(L, 3, e); 
    printf("所刪除的值為: %d\n", e); 
    printf("遍歷："); 
    ListTraverse(L, visit); 
    printf("\n"); 
 
    printf("xiaohui:\n"); 
    DestroyList(L); 
     
 
     
    system("pause"); 
    return 0; 
} 

#include <stdio.h>
#include "SqList.h"


bool equal(int a, int b){
 if(a == b)
  return true;
 return false;
}

bool visit(ElemType e){
 printf(" %d", e);
 return true;
}

int main()
{
 SqList L;
 ElemType e;
 ElemType pre_e;
 ElemType next_e;

 InitList(L);
 if(ListEmpty(L))
  printf("kong\n");

 for(int i=0;i<30;i++){
  e = i+1;
  ListInsert(L, i+1, e);
 }
 
 e = 15;
 printf("15所在的位置為： %d\n", LocateElem(L, 15, equal));
 PriorElem(L, e, pre_e);
 NextElem(L, e, next_e);
 printf("e的前驅為：%d\n", pre_e);
 printf("e的後驅為：%d\n", next_e);

 GetElem(L, 22, e);
 printf("第22個數為：%d\n", e);
   
 printf("遍歷：");
 ListTraverse(L, visit);
 printf("\n");
 printf("List length is：%d\n", ListLength(L));
 ClearList(L);
 printf("清空\n");
 printf("List length is：%d\n", ListLength(L));
 if(ListEmpty(L))
  printf("kong\n");

 ListInsert(L, 1, 3);
 ListInsert(L, 2, 7);
 ListInsert(L, 3, 9);
 ListInsert(L, 4, 1);
 ListInsert(L, 5, 44);
 printf("List length is：%d\n", ListLength(L));
 printf("遍歷：");
 ListTraverse(L, visit);
 printf("\n");

 ListDelete(L, 3, e);
 printf("所刪除的值為: %d\n", e);
 printf("遍歷：");
 ListTraverse(L, visit);
 printf("\n");

 printf("xiaohui:\n");
 DestroyList(L);
 

 
 system("pause");
 return 0;
}結果預覽：

 \
 

 

  1. 上一頁:
  2. 下一頁:
C++入門知識
uva 10995 - Educational Journey(數論)

題目連接：uva 10995 - Educationa
圖示說明C++應用程序存在的幾大重要元素

在C++應用程序裡不同類型數據進行混合運算時，C++編譯器
opencv 人臉識別 （一）訓練樣本的處理，opencv人臉

opencv 人臉識別 （一）訓練樣本的處理，opencv人
一種實現C++反射功能的想法(二)，想法

一種實現C++反射功能的想法(二)，想法　　在介紹我的思路前
C++ STL學習之一：容器的共通能力和共通操作總結

一、C++ STL各容器有一些共通的能力 其中三個最核
UVA 11889-Benefit(數學_快速枚舉因子)

UVA 11889-Benefit(數學_快速枚舉因子)

相關文章
閱讀排行榜
C++STL：仿函數 hdu 4282 A very hard mathematic problem poj 3624 (0-1背包) Problem，noproblem C語言中使用二進制常量 Codeforces Round #186 (Div. 2) (ABCDE題解) Algorithms Part 1-Question 2-QuickSort-快速排序算法 從Java到C++——枚舉類型的使用 C++ Primer 學習筆記_27_STL實踐與分析（1） --順序容器的定義、迭代器 UVA-11210-Chinese Mahjong Java and C++
熱門圖文
基於PHP給大家講解防刷票的一些技巧，php講解技巧 C#反射(Reflection)的應用(3) Delphi中IsSameDay、IsToday函數- 判斷是不是同一天、判斷是不是 c++-有關數組的維數的問題 PHP程序中的文件鎖、互斥鎖、讀寫鎖使用技巧解析， 車輛狀態：泊車、行進 next GridView動態添加列的方法及代碼
欄目導航
C++基礎知識C++入門知識關於C++
Copyright © 程式師世界 All Rights Reserved