当前位置：首页 > java >正文

《数据结构笔记二》：顺序表

java 2025/8/16 5:05:31

线性表

线性表的定义与特点

由n（n>=0）个数据特性相同的元素构成的有限序列，称为线性表

线性表是n个数据元素的有限序列，其中n个数据的是相同的数据类型

线性表中的元素个数n(n>=0),定义为线性表的长度，当n=0时称之为空表

对于非空的线性表或线性结构，其特点是：

存在唯一的一个被称之为 “第一个” 的数据元素

存在唯一的一个被称之为 “最后一个” 的数据元素

除第一个元素外，结构中的每一个数据元素均只有一个前驱

除最后一个元素外，结构中的每一个数据元素均只有一个后继

简单举例：

#include<stdio.h>#include<string.h>struct book{int              ISBN;              //书号char         bookname;       //书名double      price;              //定价}int main(int argc ; char const *argv){book B; //定义一个书的变量B.ISBN = 9527; //书号strcpy = (B.bookname,"c语言程序设计")；//书名B.price = 666; //定价return 0;}

顺序表

用一组连续的内存单元依次存储线性表的各个元素，也就是说，逻辑上相邻的元素，实际的物理存储空间也是连续的

顺序表---存储结构

#include<stdio.h>#include<string.h>#include<stdlib.h>#define MAXSIZE = 100;tydepef int     ELemType;//顺序表定义操作tydepef struct{ELemType data[MAXSIZE];int length;}SeqList;//顺序表初始化操作void initList (SeqList *L){L -> length = 0;}//在尾部添加元素操作int appendElem(SeqList *L , ElemType a){if(L->length >= MAXSIZE){printf("顺序表已满,无法添加\n")；return 0；}else{L->data[L->length] = a; //否则顺序表未满，可以添加L->lenght++; //更新 length 的值}return 1； //成功返回 1 失败返回 0        }//遍历操作void listElem(SeqList *L){for(int i = 0; i < L->length ; i++){printf("%d\n", L -> data[ i ]);    }printf("\n");}//插入数据元素操作int insertElem(SeqList *L , int position , ElemType a){if(    L->length >= MAXSIZE    ){printf(  "顺序表已满，无法插入数据\n"  );return 0;}if( position >1 || position > L->length   ){printf(    "插入位置错误\n"    );return 0 ;}if(position <= L->length){for(int i = L->length-1 ; i >= position-1 ; i--){L->data[i+1] = L->length[ i ];}L->data[position - 1] = a;L->length++ //更新 length 的值}return 1;}//删除数据元素操作int deleteElem(Seqlist *L , int position , ElemType *e){*e = L->data[position - 1]; //赋值要删除的值if(position < L->length){for(int i = position; i < L->length ; i++) //从要删除的位置一直往后循环，一直循环到最大的那个元素{L->data[i - 1] = L->data[ i ];}}L->length--;return 1;    }//查找数据位置操作int findElem(SeqList *L , ElemType a ) //传了一个表 ，传了一个元素， 然后找到这个元素位置{if(L -> length = 0) //先来一个判断是否表为空？{printf("空列表\n");return 0 ;}for(int i = 0 ; i < L -> length ; i++) //然后循环对比 挨个对比{if(L -> data[ i ] == a)         //一旦找到这个元素{return i + 1； //返回一个 i +1 ， 就是它在这个顺序表中的位置}}return 0 ；}int main(int argc ; char const *argv){//声明一个顺序表并初始化SeqList list;initList(&list);printf("初始化成功，目前长度占用%d\n",list.length);printf(“目前占用内存%zu字节\n”,sizeof(list.data));appendElem(&list,88);       appendElem(&list,77);appendElem(&list,66);appendElem(&list,55); listElem( &list );     //遍历了一下insertElem(&list , 2 ,44); //在第二个位置插入了一个44listElem( &list );    //遍历了一下ElemType delData;deleteElem(&list , 2, &delData);printf("被删除的数据元素为： %d \n", &delData);listElem( &list );    //重新遍历了一下printf("查找的这个元素的位置为：%d\n" , findElem(&list , 88))return 0;}

输出结果：

初始化成功，目前长度占用0

目前占用内存400字节

88 77 66 55

88 44 77 66 55

被删除的数据元素为：44

88 77 66 55

查找的这个元素的位置为：1

思考：顺序表插入数据的最好和最坏的时间复杂度

答：O(1) O(n)

在顺序表中，进行动态分配内存地址初始化

例子

#include <stdio.h> 
#include <stdlib.h>typedef struct 
{ int *data; int size; int capacity; 
} SeqList;// 初始化顺序表 
void SeqListInit(SeqList *list, int initialCapacity)
{ list->data = (int *)malloc(initialCapacity * sizeof(int));if (list->data == NULL) { fprintf(stderr, "内存分配失败！\n"); exit(EXIT_FAILURE); } list->size = 0;list->capacity = initialCapacity; 
}// 销毁顺序表 
void SeqListDestroy(SeqList *list)
{ free(list->data); list->data = NULL;list->size = 0;list->capacity = 0;
}// 示例：插入元素（简单扩容） 
void SeqListPushBack(SeqList *list, int value)
{ if (list->size >= list->capacity) { // 容量不足时，扩容为原来的2倍int newCapacity = list->capacity * 2; int *newData = (int *)realloc(list->data, newCapacity * sizeof(int));if (newData == NULL){ fprintf(stderr, "扩容失败！\n");exit(EXIT_FAILURE); } list->data = newData;list->capacity = newCapacity; } list->data[list->size++] = value; 
}int main(int argc , char  const *argv) 
{ SeqList list; SeqListInit(&list, 4); // 初始容量设为4// 插入元素测试 SeqListPushBack(&list, 10); SeqListPushBack(&list, 20); printf("当前元素个数: %d, 容量: %d\n", list.size, list.capacity);SeqListDestroy(&list); // 释放内存 return 0;
}

运行结果