顺序表的基本运算

线性表的定义

  1. #include <stdio.h>
  2. #define MAXSIZE 100 /*顺序表的容量*/
  4. typedef char ElemType;
  6. typedef struct
  7. {
  8.     ElemType data[MAXSIZE]; /*存放顺序表的元素*/
  9.     int length;                /*顺序表的实际长度*/
  10. } SqList;

初始化线性表

  1. void InitList(SqList &sq) /*初始化线性表*/
  2. {
  3.     sq.length = 0;
  4. }

求线性表长度

  1. int GetLength(SqList sq) /*求线性表长度*/
  2. {
  3.     return sq.length;
  4. }

求线性表中第i个元素

  1. int GetElem(SqList sq, int i, ElemType &e) /*求线性表中第i个元素*/
  2. {
  3.     if (i < 1 || i > sq.length) /*无效的i值*/
  4.         return 0;
  5.     else
  6.     {
  7.         e = sq.data[i - 1];
  8.         return 1;
  9.     }
  10. }

按值查找

  1. int Locate(SqList sq, ElemType x) /*按值查找*/
  2. {
  3.     int i = 0;
  4.     while (sq.data[i] != x) /*查找值为x的第1个结点*/
  5.         i++;
  6.     if (i > sq.length)
  7.         return (0); /*未找到*/
  8.     else
  9.         return (i + 1);
  10. }

插入元素

  1. int InsElem(SqList &sq, ElemType x, int i) /*插入元素*/
  2. {
  3.     int j;
  4.     if (i < 1 || i > sq.length + 1) /*无效的参数i*/
  5.         return 0;
  6.     for (j = sq.length; j > i; j--) /*将位置为i的结点及之后的结点后移*/
  7.         sq.data[j] = sq.data[j - 1];
  8.     sq.data[i - 1] = x; /*在位置i处放入x*/
  9.     sq.length++;        /*线性表长度增1*/
  10.     return 1;
  11. }

删除元素

  1. int DelElem(SqList &sq, int i) /*删除元素*/
  2. {
  3.     int j;
  4.     if (i < 1 || i > sq.length) /*无效的参数i*/
  5.         return 0;
  6.     for (j = i; j < sq.length; j++) /*将位置为i的结点之后的结点前移*/
  7.         sq.data[j - 1] = sq.data[j];
  8.     sq.length--; /*线性表长度减1*/
  9.     return 1;
  10. }

输出线性表

  1. void DispList(SqList sq) /*输出线性表*/
  2. {
  3.     int i;
  4.     for (i = 1; i <= sq.length; i++)
  5.         printf("%c ", sq.data[i - 1]);
  6.     printf("\n");
  7. }

main

  1. void main()
  2. {
  3.     int i;
  4.     ElemType e;
  5.     SqList sq;
  6.     InitList(sq);         /*初始化顺序表sq*/
  7.     InsElem(sq, 'a', 1); /*插入元素*/
  8.     InsElem(sq, 'c', 2);
  9.     InsElem(sq, 'a', 3);
  10.     InsElem(sq, 'e', 4);
  11.     InsElem(sq, 'd', 5);
  12.     InsElem(sq, 'b', 6);
  13.     printf("线性表:");
  14.     DispList(sq);
  15.     printf("长度:%d\n", GetLength(sq));
  16.     i = 3;
  17.     GetElem(sq, i, e);
  18.     printf("第%d个元素:%c\n", i, e);
  19.     e = 'a';
  20.     printf("元素%c是第%d个元素\n", e, Locate(sq, e));
  21.     i = 4;
  22.     printf("删除第%d个元素\n", i);
  23.     DelElem(sq, i);
  24.     printf("线性表:");
  25.     DispList(sq);
  26. }