程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 數據結構讀書筆記(一)(C語言)

數據結構讀書筆記(一)(C語言)

編輯:C++入門知識

                                                                      第一章   關於數據結構   1.數據結構研究什麼?(計算機加工的對象由數值——>非數值)       將現實生活中大量而復雜的問題(非數值問題)以特定的數據類型(邏輯結構)和特定的存儲結構(物理結構)保存到主存儲器中,以及在此基礎上為實現某個功能(刪除、排序)相對應的操作。   2.數據的邏輯結構:     3.存儲結構(物理結構):    1)順序存儲結構(借助元素在存儲器中的相對位置)    2)鏈式存儲結構(借助元素存儲地址的指針)   4.抽象數據類型ADT:   [cpp]   ADT抽象數據類型名   {      數據對象:<數據對象的定義>      數據關系:<數據對象之間關系的定義>      基本操作:<基本操作的定義>   }   5、時間復雜度:   取決定性作用語句的重復次數                                                                                     第二章    線性表   1.線性結構的基本特征:   1)集合中必存在唯一的一個“第一個元素”;   2)集合中必存在唯一的一個“最後元素”;   3)除最後元素外,均有唯一的後繼;   4)除第一元素之外,均有唯一的前驅;    2.ADT   [cpp]   ADT List   {     數據對象:D={ a1,a2, a3, ... an};     數據關系:R={<a1, a2>, <a2, a3>, <a3, a4> … <an-1, an>};      基本操作:     InitList(&L);         //操作結果:構造線性表;     DestroyList(&L);     //操作結果:銷毀線性表;     ListEmpty(L);        //操作結果:若L為空表,則返回TRUE,否則FALSE;     ListLength(L);       //操作結果:返回L中元素個數;               PriorElem(L,cur_e,&pre_e)//操作結果:cur_e是L的元素,但不是第一個                              //則用pre_e返回它的前驅。若操作失敗,pre_e無定義     NextElem(L,cur_e,&next_e)//操作結果:cur_e是L的元素,但不是最後一個,                              //則用next_e返回它的後繼。若操作失敗,next_e無定義       GetElem(L,i,&e) //  1<= i <=LengthList(L) 操作結果:用e返回L中第i個元素的值。     LocateElem(L,e,compare())//compare()是元素判定函數。返回L中第一個與e滿足compare()的元素位序。                              //若這樣的元素不存在,則返回值為0。     ListTraverse(L,visit( )) //依次對L的每個元素調用函數visit( ).一旦visit( )失敗,則操作失敗     ClearList(&L)         //操作結果將L重置為空表。     PutElem(L,i,&e)    //1<=i<=LengthList(L)  結果:L中第i個元素賦值為e     ListInsert(&L,i,e) //1<=i <=LengthList(L) +1  結果:在L的第i個元素之前插入新的元素e,L的長度增1     ListDelete(&L,i,&e)//1<=i <=LengthList(L) 結果:刪除L的第i個元素,並用e返回其值,,L的長度減1   }ADT List   3.順序實現    1)存儲結構:     [cpp]   #define LIST_INIT_SIZE   10   #define INCREAMENT   2   struct SqList   {       ElemType * elem;       int length;       int listsize;   };    2)基本操作   [cpp]   void InitList(SqList & L )   {       L.elem   = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType) );       L.length = 0;       L.listsize = LIST_INIT_SIZE;   }   void DestroyList(SqList & L)   {       free(L.elem);       L.elem = NULL;       L.length = 0;       L.listsize = 0;   }   void ClearList( SqList & L)   {       L.length = 0;   }   Status ListEmpty( SqList L)   {       if( L.length != 0 )           return FALSE;       else           return TRUE;   }   int ListLength(SqList L)   {       return L.length;   }   Status GetElem(SqList L, int i , ElemType & e)   {       if( i < 1 || i > L.length )           return ERROR;       e = *(L.elem + i - 1);       return OK;   }    int LocateElem(SqList L,ElemType e, Status(*compare)(ElemType , ElemType))   {       ElemType * p;       p = L.elem;       int i = 1;       while(i < L.length && !(compare(e, *p)))       {           i++;           p++;        }       if( i< L.length)           return i;       else           return 0;   }   Status PriorElem(SqList L, ElemType cur_e, ElemType & pre_e)   {       ElemType * p;       p = L.elem + 1;   //p 和 i 之間進行合作       int i = 2;       while(i < L.length && *p!=cur_e)       {           i++;           p++;        }       if( i< L.length)       {           pre_e = *(--p);           return OK;       }       else           return INFEASIBLE;   }   Status NextElem(SqList L,ElemType cur_e,ElemType &next_e)    { // 初始條件:順序線性表L已存在      // 操作結果:若cur_e是L的數據元素,且不是最後一個,則用next_e返回它的後繼,      //           否則操作失敗,next_e無定義      int i=1;      ElemType *p=L.elem;      while(i<L.length&&*p!=cur_e)      {        i++;        p++;      }      if(i==L.length)        return INFEASIBLE; // 操作失敗      else      {        next_e=*++p;        return OK;      }    }   Status ListInsert(SqList & L, int i , ElemType e)   {       if(i < 1 || i > L.length + 1)           return ERROR;       ElemType * newbase;       if(L.length >= L.listsize)       {                  newbase = (ElemType *)realloc(L.elem,( L.listsize + INCREAMENT) * sizeof(ElemType));         L.listsize = L.listsize + INCREAMENT;          if(!newbase)           exit(OVERFLOW);         L.elem = newbase;       }       ElemType * p,*q;       p = L.elem + L.length -1;       q = L.elem + i -1;       for(p = L.elem + L.length -1; p >= q;  --p)       {           *(p + 1) = * p;        }          *q = e;       L.length = L.length + 1;       return OK;   }    Status ListDelete(SqList &L,int i,ElemType &e) // 算法2.5    { // 初始條件:順序線性表L已存在,1≤i≤ListLength(L)      // 操作結果:刪除L的第i個數據元素,並用e返回其值,L的長度減1      ElemType *p,*q;      if(i<1||i>L.length) // i值不合法        return ERROR;      p=L.elem+i-1; // p為被刪除元素的位置      e=*p; // 被刪除元素的值賦給e      q=L.elem+L.length-1; // 表尾元素的位置      for(++p;p<=q;++p) // 被刪除元素之後的元素左移        *(p-1)=*p;      L.length--; // 表長減1      return OK;    }    void ListTraverse(SqList L,void(*vi)(ElemType & ))    { // 初始條件:順序線性表L已存在      // 操作結果:依次對L的每個數據元素調用函數vi()      //           vi()的形參加'&',表明可通過調用vi()改變元素的值      ElemType *p;      int i;      p=L.elem;      for(i=1;i<=L.length;i++)        vi(*p++);      printf("\n");    }   4.鏈式實現     1)存儲結構:   [cpp]   struct LNode   {       ElemType data;       LNode * next;   };      typedef LNode * LinkList ;         2)基本操作:   [cpp]   void InitList(LinkList &L)    { // 操作結果:構造一個空的線性表L      L=(LinkList)malloc(sizeof(LNode)); // 產生頭結點,並使L指向此頭結點      if(!L) // 存儲分配失敗        exit(OVERFLOW);      L->next=NULL; // 指針域為空    }    void DestroyList(LinkList &L)    { // 初始條件:線性表L已存在。操作結果:銷毀線性表L      LinkList q;      while(L)      {        q=L->next;        free(L);        L=q;      }    }    void ClearList(LinkList L) // 不改變L    { // 初始條件:線性表L已存在。操作結果:將L重置為空表      LinkList p,q;      p=L->next; // p指向第一個結點      while(p) // 沒到表尾      {        q=p->next;        free(p);        p=q;      }      L->next=NULL; // 頭結點指針域為空    }    Status ListEmpty(LinkList L)    { // 初始條件:線性表L已存在。操作結果:若L為空表,則返回TRUE,否則返回FALSE      if(L->next) // 非空        return FALSE;      else        return TRUE;    }    int ListLength(LinkList L)    { // 初始條件:線性表L已存在。操作結果:返回L中數據元素個數      int i=0;      LinkList p=L->next; // p指向第一個結點      while(p) // 沒到表尾      {        i++;        p=p->next;      }      return i;    }    Status GetElem(LinkList L,int i,ElemType &e) // 算法2.8    { // L為帶頭結點的單鏈表的頭指針。當第i個元素存在時,其值賦給e並返回OK,否則返回ERROR      int j=1; // j為計數器      LinkList p=L->next; // p指向第一個結點      while(p&&j<i) // 順指針向後查找,直到p指向第i個元素或p為空      {        p=p->next;        j++;      }      if(!p||j>i) // 第i個元素不存在        return ERROR;      e=p->data; // 取第i個元素      return OK;    }    int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))    { // 初始條件: 線性表L已存在,compare()是數據元素判定函數(滿足為1,否則為0)       /*操作結果: 返回L中第1個與e滿足關系compare()的數據元素的位序。                若這樣的數據元素不存在,則返回值為0*/      int i=0;      LinkList p=L->next;      while(p)      {        i++;        if(compare(p->data,e)) // 找到這樣的數據元素          return i;        p=p->next;      }      return 0;    }   Status PriorElem(LinkList L,ElemType cur_e,ElemType &pre_e)    { // 初始條件: 線性表L已存在      /* 操作結果: 若cur_e是L的數據元素,且不是第一個,則用pre_e返回它的前驅,                返回OK;否則操作失敗,pre_e無定義,返回INFEASIBLE*/      LinkList q,p=L->next; // p指向第一個結點      while(p->next) // p所指結點有後繼      {        q=p->next; // q為p的後繼        if(q->data==cur_e)        {          pre_e=p->data;          return OK;        }        p=q; // p向後移      }      return INFEASIBLE;    }    Status NextElem(LinkList L,ElemType cur_e,ElemType &next_e)    { // 初始條件:線性表L已存在    /*   操作結果:若cur_e是L的數據元素,且不是最後一個,則用next_e返回它的後繼,                返回OK;否則操作失敗,next_e無定義,返回INFEASIBLE*/      LinkList p=L->next; // p指向第一個結點      while(p->next) // p所指結點有後繼      {        if(p->data==cur_e)        {          next_e=p->next->data;          return OK;        }        p=p->next;      }      return INFEASIBLE;    }   Status ListInsert(LinkList L,int i,ElemType e) // 算法2.9。不改變L    { // 在帶頭結點的單鏈線性表L中第i個位置之前插入元素e      int j=0;      LinkList p=L,s;      while(p&&j<i-1) // 尋找第i-1個結點      {        p=p->next;        j++;      }      if(!p||j>i-1) // i小於1或者大於表長        return ERROR;      s=(LinkList)malloc(sizeof(LNode)); // 生成新結點      s->data=e; // 插入L中      s->next=p->next;      p->next=s;      return OK;    }    Status ListDelete(LinkList L,int i,ElemType &e) // 算法2.10。不改變L    { // 在帶頭結點的單鏈線性表L中,刪除第i個元素,並由e返回其值      int j=0;      LinkList p=L,q;      while(p->next&&j<i-1) // 尋找第i個結點,並令p指向其前驅      {        p=p->next;        j++;      }      if(!p->next||j>i-1) // 刪除位置不合理        return ERROR;      q=p->next; // 刪除並釋放結點      p->next=q->next;      e=q->data;      free(q);      return OK;    }    void ListTraverse(LinkList L,void(*vi)(ElemType))     //vi的形參類型為ElemType,與bo2-1.cpp中相應函數的形參類型ElemType&不同    { // 初始條件:線性表L已存在。操作結果:依次對L的每個數據元素調用函數vi()      LinkList p=L->next;      while(p)      {        vi(p->data);        p=p->next;      }      printf("\n");    }      

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved