数据结构与算法（一）线性表顺序存储

• 接口

#ifndef _LINEAR_ARRAY_H_
#define _LINEAR_ARRAY_H_
#include <stdlib.h>
#include <stdio.h>
#include<stdbool.h>
#define MAXSIZE 100
#define ElementType int
typedef struct LNode*List;
struct LNode {
    ElementType Data[MAXSIZE];
    int Last;
};
List PtrL;

List MakeEmpty();//初始化一个空线性表L
ElementType FindKth(int K, List L);//根据位序K，返回相应元素
int Find(ElementType X, List L);//在线性表L中查找X的第一次出现位置；
void Insert(ElementType X, int i, List L);//在位序i前插入一个新元素X；
void Delete(int i, List L);//删除指定位序i的元素
int Length(List L);//返回线性表L的长度
bool isFull(List L);//线性表L是否满
bool isEmpty(List L);//线性表是为空
#endif

• 函数实现

 

#include "LinearArray.h" 
List MakeEmpty() 
{ 
   List ptrl = NULL; 
   ptrl = (List)malloc(sizeof(struct LNode)); 
   ptrl->Last = -1; 
   return ptrl; 
} 
int Length(List L) 
{ 
   printf("list length is %d.", L->Last + 1); 
   return L->Last+1; 
} 
bool isEmpty(List L) 
{ 
   return L->Last == 0 ? true : false; 
} 
bool isFull(List L) 
{ 
   return L->Last == MAXSIZE - 1 ? true : false; 
} 
void Insert(ElementType X,int i, List L) 
{ 
   if (isFull(L)){ 
       printf("list is full.\n"); 
       return; 
   } 
   if (i < 1 || i > L->Last + 2){ 
       printf("insert index is illegal.\n"); 
       return; 
   } 
   for (int index = L->Last; index >= i - 1; index--){ 
       L->Data[index+1] = L->Data[index]; 
   } 
   L->Data[i - 1] = X;         
   L->Last ++; 
   return; 
} 
void Delete(int i, List L) 
{ 
   if (isEmpty(L)){ 
       printf("list is empty.\n"); 
       return; 
   } 
   if (i < 1 || i > L->Last+1){ 
       printf("delete index is not exist.\n"); 
       return -1; 
   } 
   for (int index = i - 1; index <= L->Last; index++) 
   { 
       L->Data[index] = L->Data[index+1]; 
   } 
   L->Last--; 
   return; 
} 

ElementType Find(ElementType X, List L) 
{ 
   if (isEmpty(L)) 
   { 
       printf("list is empty.\n"); 
       return -1; 
   } 
   for (int index = 0; index <= L->Last; index++){ 
       if (L->Data[index] == X){ 
           return index; 
       } 
   } 
   return -1; 
} 
ElementType FindKth(int K, List L) 
{ 
   if (isEmpty(L)){ 
       printf("list is empty.\n"); 
       return -1; 
   } 
   if ( K < 1 ||K > L->Last+1){ 
       printf("find index is not exist.\n"); 
       return -1; 
   } 
   return L->Data[K - 1]; 
} 
void Display(List L) 
{ 
   for (int index = 0; index <= L->Last; index++){ 
       printf("%d ", L->Data[index]); 
   } 
   printf("\n"); 
}

• 测试函数

int main(int argc, char**argv) 
{ 
   List myList = MakeEmpty(); 
   for (int i = 0; i <= 9; i++) 
   { 
       Insert(i, i+1, myList); 
   } 
   Display(myList); 
   Delete(5, myList); 
   Display(myList); 
   Insert(27, 8, myList); 
   Display(myList); 
   return 0; 
}

• 测试结果

• GitHub地址：

https://github.com/baiyu2017/baiyu2021.git