logo
JxbzshBlog
banner
NEWS LETTER

线性表

Scroll down

线性表

顺序结构

  • 结构定义

    1
    2
    3
    4
    5
    6
    7
    #define MAXSIZE  100

    typedef struct SeqList {
        ElemType elem[MAXSIZE];  //线性表占用的数组空间
        int last;    //记录线性表中最后一个元素在数组elem[]中的位置（下标值），空表置为-1
    } SeqList, LList, *LListPtr;

  • 查找

    • 按序号查找

    • 按内容查找

      1. 遍历数组元素
      2. 找到与所找元素值相同的元素
      3. 返回元素位置
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      int Locate( SeqList L,ElemType e) {
          /*在顺序表L中查找与e相等的元素,若L.elem[i] = e,则找到该元素,并返回i + 1,若找不到,则返回-1*/
          i = 0;	/*i为扫描计数器,初值为0,即从第一个元素开始比较*/

          while((i <= L.last) && (L.elem[i] != e)) {/*顺序扫描表,直到找到值为e的元素,或扫描到表尾而没找到*/
          	i++;
          }
          if(i <= L.last) {
          	return(i + 1);	/*若找到值为e的元素,则返回其序号*/
          } else {
              return(-1);		/*若没找到,则返回空序号*/
          }
      }

  • 插入

    1. 找到要插入的位置
    2. 将该位置后的所有元素依次后移
    3. 将元素插入
    4. 更新数组长度
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    #define OK 1
    #define ERROR 0

    int lnsList(SeqList* L, int i, ElemType e) {
     	/*在顺序表L中第i个数据元素之前插入一个元素e。i的合法取值范围是1 ≤ i ≤ L->last + 2*/
    	int k;
    	if((i < 1) || (i > L->last + 2)) {		/*首先判断插入位置是否合法*/
        	printf("插入位置i值不合法");
    		return(ERROR);
    	}

    	if(L->last >= MAXSIZE - 1) {
            printf("表已满,无法插入");
    		return(ERROR);
        }
        
    	for(k = L->last; k >= i - 1; k--) {		/*为插入元素而移动位置*/
            L->elem[k + 1] = L->elem[k];
        }
        
        L->elem[i - 1] = e;		/*在C语言数组中,第i个元素的下标为i-1*/
        L->last++;
    	return(OK);
    }

  • 删除

    1. 找到要插入的位置
    2. 将该位置后的所有元素依次前移
    3. 更新数组长度
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    int DelList(SeqList * L,int i,ElemType * e) {
        /*在顺序表L中删除第i个数据元素,并用指针参数e返回其值。i的合法取值为1 ≤ i ≤ L.last + 1*/
    	int k;
    	if((i < 1) || (i > L->last + 1)){
            printf("删除位置不合法!");
            return(ERROR);
        }
    	
    	*e = L->elem[i - 1];	/*将删除的元素存放到e所指向的变量中*/
        for(k = i; i <= L->last; k++) {
    		L->elem[k - 1] = L->elem[k];	/*将后面的元素依次前移*/
        }
        
        L->last--;
    	Return( OK);
    }

链式结构

单链表（带头结点）

  • 结构定义

    1
    2
    3
    4
    typedef struct _node {
        ElemType data;
        struct _node   *next;
    } Node, *NodePtr, LList, *LListPtr;

  • 初始化

    1
    2
    3
    4
    5
    void InitList(LListPtr *L) {
        //生成头结点，并将头结点的指针域置为空
        *L = (NodePtr)malloc(sizeof(Node));
        (*L)->next = NULL;
    }

  • 查找（简单遍历）

  • 插入

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    bool InsList(LListPtr L, int i, ElemType e) {
        NodePtr p = L;
        int k = 1;
        
        //从头开始移动工作指针，同时计数，数到i-1，即找到要插入位置的前一个位置
        for (; p != NULL && k < i; ++k) {
            p = p->next;
        }

        //如果遍历完了链表，还没有数到i-1，则说明插入位置不合理
        if (p == NULL) {
            return false;
        }

        //生成新节点并插入到结点p之后
        NodePtr q = (NodePtr)malloc(sizeof(Node));
        q->data = e;
        q->next = p->next;
        p->next = q;

        return true;
    }

  • 删除

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    bool DelList(LListPtr L, int i, ElemType *e) {
        NodePtr p = L;
        int k = 1;

        for (; p->next != NULL && k < i; ++k) {
            p = p->next;
        }

        //如果遍历完了链表，还没有数到i-1，则说明删除位置不合理
        if (p->next == NULL) {
            return false;
        }

        NodePtr q = p->next;
        p->next = q->next;
        *e = q->data;
        free(q);

        return true;
    }

循环链表

  • 结构定义

    1
    2
    3
    4
    typedef struct _node {
        ElemType data;
        struct _node  *next;
    } Node, *NodePtr, LList, *LListPtr;

  • 初始化

    1
    2
    3
    4
    void InitList(LListPtr *L) {
        (*L) = (NodePtr)malloc(sizeof(Node));
        (*L)->next = *L;	//头结点的指针域指向头节点为空
    }

  • 插入

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    bool InsList(LListPtr L, int i, ElemType e) {
        NodePtr p = L; //TODO
        int k = 1; //TODO

        //TODO
        for (; p->next != L && k < i; ++k)
            p = p->next;

        if (p->next == L && k < i) return false;

        NodePtr q = (NodePtr)malloc(sizeof(Node));
        q->data = e;
        q->next = p->next;
        p->next = q;

        return true;
    }



    /*
     * 这里解释一下循环的条件判断（不考虑i<1）
     * 1. 假设链表里有5个节点。图中，L代表头结点，数字表示节点的数据域，------>表示指针域。^表示下方工作指针的指向。
     * 1) 如果i=1（边缘条件，但却是可接受位置）
     * i=1
     *  L------>1------>2------>3------>4------>5------>L
     *  ^       ^
     *  p    p->next
     * k=1
     * p->next!=L成立，但k<i（即1<1）不成立，循环结束。
     * 在后续的那条if (p->next == L && k < i)中，p->next==L不成立，因此不执行返回false。p停在了节点L上，这是正确的插入位置。
     *
     * 2) 如果i=3（1<i<=5，在正常范围）
     *                         i=3
     *  L------>1------>2------>3------>4------>5------>L
     *  ^       ^
     *  p    p->next
     * k=1
     * 那么进行第一次循环判断时，两个条件都会成立，循环继续。当进行到这里时：
     *                         i=3
     *  L------>1------>2------>3------>4------>5------>L
     *                  ^       ^
     *                  p    p->next
     *                 k=3
     * p->next!=L成立, 但k<i（即3<3）不成立，循环结束。
     * 在后续的那条if (p->next == L && k < i)中，p->next==L不成立，因此不执行返回false。p停在节点2上。这是正确的插入位置。
     *
     * 3) 如果i=6。链表里有5个节点，所以这个插入位置是可以接受的，即表示新节点插在5节点之后，L节点“之前”。
     * 那么当进行到这里时：
     *                                                 i=6
     *  L------>1------>2------>3------>4------>5------>L
     *                                          ^       ^
     *                                          p    p->next
     *                                         k=6
     * p->next!=L不成立，循环结束。
     * 在后续的那条if (p->next == L && k < i)中，p->next==L成立，但k<i（即6<6）不成立，因此不执行返回false，p停在了节点5上，这是正确的插入位置。
     *
     * 4) 如果i>6，假设为7，超出节点数量。
     * 参考3)，当p->next==L成立时，循环结束。此时，k=6，没有计数到7，即此时k<i也成立。这就是后面“插入位置不合理”判断的依据。
     *
     * 2. 极端情况：链表为空时
     * 1) 如果i=1，插入位置是可接受的。
     * i=1
     *  L------>L
     *  ^       ^
     *  p    p->next
     * k=1
     * p->next!=L不成立，循环结束。
     * 在后续的那条if (p->next == L && k < i)中，p->next==L成立，但k<i（即1<1）不成立，因此不执行返回false，p停在了节点L上，这是正确的插入位置。
     *
     * 2) 如果i=任意>1的数，例如2
     *         i=2
     *  L------>L
     *  ^       ^
     *  p    p->next
     * k=1
     * p->next!=L不成立，循环结束。
     * 在后续的那条if (p->next == L && k < i)中，p->next==L成立，k<i（即1<2）也成立，因此执行返回false。
    */

  • 删除

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    bool DelList(LListPtr L, int i, ElemType *e) {
        NodePtr p = L;
        int k = 1;

        for (; p->next != L && k < i; ++k)
            p = p->next;

        if (p->next == L) return false;

        NodePtr q = p->next;
        p->next = q->next;
        free(q);

        return true;
    }

双向链表

  • 结构定义

    1
    2
    3
    4
    5
    typedef struct _node
    { 
    	ElemType data;
    	struct _node  *next, *prior;
    } Node, *NodePtr, LList, *LListPtr;

  • 初始化

    1
    2
    3
    4
    void InitList(LListPtr *L) {
        (*L) = (NodePtr)malloc(sizeof(Node)); //生成头结点
        (*L)->prior = (*L)->next = NULL; //头结点的指针域为空
    }

  • 插入

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    bool InsList(LListPtr L, int i, ElemType e) {
        NodePtr p = L;
        int k = 1;

        while (p != NULL && k < i) {
            p = p->next;
            ++k;
        }

        if (p == NULL) return false;

        NodePtr s = (NodePtr)malloc(sizeof(Node));
        s->data = e;
        
        if (p->next == NULL) { //p指向最后一个结点
            s->next = NULL;
            s->prior = p;
            p->next = s;
        } else {
            s->next = p->next;
            s->prior = p;
            p->next->prior = s;
            p->next = s;
        }

        return true;
    }

  • 删除

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    bool DelList(LListPtr L, int i, ElemType *e) {
        NodePtr p = L;
        int k = 1;

        while (p != NULL && k < i) {
            p = p->next;
            ++k;
        }

        if (p == NULL || p->next == NULL) return false;

    	//TODO
        p = p->next;

        p->next->prior = p->prior;
        p->prior->next = p->next;

    	free(p);

        return true;
    }
其他文章
cover
栈与队列
  • 24/06/21
  • 09:46
  • 数据结构
cover
数据结构
  • 24/06/19
  • 14:35
  • 数据结构
© 2024- 2024 Jxbzsh
由 Hexo 驱动 v7.2.0 主题 - Async v2.1.10
目录导航 置顶
  1. 1. 线性表
    1. 1.1. 顺序结构
    2. 1.2. 链式结构
      1. 1.2.1. 单链表（带头结点）
      2. 1.2.2. 循环链表
      3. 1.2.3. 双向链表
请输入关键词进行搜索
  • to close