大话数据结构学习笔记2

77 阅读 0 评论 51 点赞

我是靠谱客的博主缥缈季节，最近开发中收集的这篇文章主要介绍大话数据结构学习笔记2，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

什么是线性表
零个或多个元素的有限序列
线性表的长度、直接前驱元素、直接后继元素、位序
线性表的元素个数即为长度（大于或等于0）；（a1,a2,a3,...,an-1，an）称an-1是an的直接前继元素，an是an-1的直接后继元素。n为位序。

线性表顺序存储结构的增删改查算法步骤和代码实现

插入：如果要插入的位置ith小于1或者大于最后一个元素的下一位置，抛异常或者返回错误。如果数组已经满，抛异常或者退出。从最后一个元素开始到第ith个元素，逐个向后移动一位。将数据插入第ith位置。数组长度加1.返回成功

删除：如果要删除的位置ith小于1或者大于最后一个元素，抛异常或者返回错误。如果数组已经空，抛异常或者退出。取出第ith个元素放到data中，表明删除了什么。从第ith+1个元素开始到最后一个元素，逐个向前移动一位覆盖。数组长度减1.返回成功

查询：如果要查询的位置ith小于1或者大于最后一个元素，抛异常或者返回错误。将第ith个元素的数据放到入参指针data指向的地址中。返回成功。

更改：如果要更改的位置ith小于1或者大于最后一个元素，抛异常或者返回错误。将入参data放入第ith个元素的数据中。返回成功。

/**/
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define SIZE 10
/*数组实现顺序存储*/
typedef int ElemType;
typedef struct {
ElemType Data[SIZE];
int length;
}SqList;
/*顺序存储结构插入*/
/*初始条件：线性表SqL已经存在，1<=ith<=length+1,data传入要插入的数据*/
/*操作结果：在ith位置之前插入数据data，长度length加1*/
int InsertSqlist(SqList* SqL, int ith, ElemType data)
{
if (ith<1|| ith>SqL->length+1 || SqL->length == SIZE)/*如果请求插入位置比1小或者比最后一位的下一位还大，或者数组已满*/
{
return ERROR;
}
for (int i = SqL->length - 1; i > ith - 1 - 1; i--)/*从最后一位到第ith位，依次向后移动*/
{
SqL->Data[i + 1] = SqL->Data[i];
}
SqL->Data[ith - 1] = data;
SqL->length++;
return OK;
}
/*顺序存储结构删除,并接收删除内容*/
/*初始条件：SqL已经存在，1<=ith<=length。*/
/*操作结果：删除第ith个元素，并将内容放在data中，长度减小1*/
int DeleteSqList(SqList* SqL, int ith, ElemType* data) {
if (ith <1 || ith > SqL->length)/*如果删除位置比1小或者比最后一位大或数组已空*/
{
return ERROR;
}
*data = SqL->Data[ith - 1];
for (int i = ith - 1; i < SqL->length ; i++)/*从第ith位到最后一位，依次前移*/
{
SqL->Data[i] = SqL->Data[i + 1];
}
SqL->length--;
return OK;
}
/*顺序存储的查询操作*/
/*初始条件：SQL已存在，1<=ith<=length.*/
/*操作结果：将查询结果第ith个元素放到data中*/
int getElem(SqList* SqL, int ith, ElemType* data) {
if (ith <1 || ith > SqL->length)/*如果查询位置比1小或者比最后一个位置大或数组已空*/
{
return ERROR;
}
*data = SqL->Data[ith - 1];
return OK;
}
/*顺序存储的更改操作*/
/*初始条件：SQL已存在，1<=ith<=length.*/
/*操作结果：第ith个元素更改为data*/
int setElem(SqList* SqL, int ith, ElemType data) {
if (ith <1 || ith > SqL->length)/*如果查询位置比1小或者比最后一个位置大或数组已空*/
{
return ERROR;
}
SqL->Data[ith - 1] = data;
return OK;
}
void ShowList(SqList SqL) {
for (int i = 0; i < SqL.length; i++)
{
printf("data[%d]=%dt", i, SqL.Data[i]);
}
printf("n");
return;
}
int main() {
SqList testlist;
testlist.Data[0] = 0;
testlist.length = 1;
for (int i = 5; i >=1; i--)
{
InsertSqlist(&testlist, 1, i);
}
ShowList(testlist);
printf("数组长度=%dn",testlist.length);
printf("第6位改为6.n");
setElem(&testlist,6,6);
ShowList(testlist);
ElemType temp; getElem(&testlist, 6, &temp);
printf("获取第6位=%dn",temp);
DeleteSqList(&testlist, 3, &temp);
printf("删除第3位=%dn",temp);
printf("删除之后数组：n");
ShowList(testlist);
printf("在第2位插入77后数组为：n");
InsertSqlist(&testlist,2,77);
ShowList(testlist);
printf("删除最后一位，数组为：n");
DeleteSqList(&testlist, testlist.length, &temp);
ShowList(testlist);
printf("在表尾部插入99后n");
InsertSqlist(&testlist,testlist.length+1,99);
ShowList(testlist);
system("Pause");
return 0;
}

注意for循环范围。

线性表链式存储结构的增删改查算法步骤和代码实现

链式存储使用结构体和结构体指针抽象数据。

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define SIZE 10
/*带有指针的结构体实现节点，结构体指针实现链表*/
typedef struct Node{
ElemType Data;
struct Node * next;
}Node;
typedef Node* LinkedList;
/*查询链表中第i个元素*/
/*前提条件：存在链表*/
/*操作结果：将查询到的结果放在形参指针rs指向的地址中*/
/*
步骤：1.头指针指向头结点2.指针每向后移动一次，计数加一3.直到指针为空或者计数不小于ith 4.将查询内容放入rs指针5.返回状态码*/
int getElem(LinkedList L,int ith,ElemType* rs) {
int counter = 1;
LinkedList p = L->next;/*指向第一个节点*/
while (p&&counter<ith)/*当指针没有指向尾结点的下一节点（NULL）并且数小于ith时，移动指针并计数加一*/
{
p = p->next;
counter++;
}
if (!p)
{
return ERROR;
}
*rs = p->Data;
printf("节点数据=%dt", *rs);
printf("地址=%xt",p);
printf("next指针=%xn",p->next);
return OK;
}
///****************************************************************************
/// @data
:
/// @input
:L 链表指针；ith 插入位置；data 需要插入的数据
/// @output
: OK 操作成功 ERROR 操作失败
/// @brief
: 1<=ith<=length，操作后链表在第ith位置处增加一个节点
///****************************************************************************
int InsertLinkedList(LinkedList* L,int ith,ElemType _data) {
int counter = 1;
LinkedList p = *L;/*指向头结点*/
while (p &&counter < ith)/*当指针没有指向尾结点的下一节点（NULL）并且小于第i个节点的直接前继时，移动指针并计数加一*/
{
p = p->next;
counter++;
}
if (!p)
{
return ERROR;
}
/*此时已经指向第i个节点的直接前继*/
LinkedList NewNode = (LinkedList)malloc(sizeof(Node));/*开辟内存，创建新的节点*/
NewNode->Data = _data;/*传入数据*/
NewNode->next = p->next;/*新节点next指针指向原来的第i个节点*/
p->next = NewNode;/*第i个节点的直接前继的next指针重定向到新节点*/
return OK;
}
///****************************************************************************
/// @data
:
/// @input
:L 链表指针；ith 删除第i个节点；data 需要插入的数据
/// @output
: OK 操作成功 ERROR 操作失败
/// @brief
: 1<=ith<=length，操作后链表在第ith位置处增加一个节点
///****************************************************************************
int DeleteLinkedList(LinkedList* L, int ith, ElemType* _data) {
int counter = 1;
LinkedList p = *L;
while (p && counter < ith )
{
p = p->next;
counter++;
}
if (!p)
{
return ERROR;
}
/*此时p已经指向第i个节点的直接前继*/
LinkedList pDel = p->next;/*指向第i个要删除的节点*/
p->next = pDel->next;/*第i个节点的直接前继节点的next指针，指向直接后继*/
*_data = pDel->Data;/*传出要删除的数据*/
free(pDel);/*删除第i个节点*/
return OK;
}
///****************************************************************************
/// @data
:
/// @input
: n：节点数量
/// @output
:OK Error
/// @brief
:使用头插法，创建一个内容data从1到n 的链表，作为检验上述增删改查的数据
///****************************************************************************
int CreatesqLinkList(LinkedList* L,int n) {
for (int i = n; i > 0; i--)
{
if(!InsertLinkedList(L, 1, i)) return ERROR;
}
return OK;
}
///****************************************************************************
/// @data
:
/// @input
:L 头指针的地址
n要创建的节点数量
/// @output
:返回创建操做是否成功OK、ERROR
/// @brief
:使用尾插法，对空链表进行整表创建。前提已经存在空链表，传入一个空链表的头指针地址。
///****************************************************************************
void CreatBackpushLinkList(LinkedList*L,int n) {
LinkedList p = *L;
srand(time(0));
for (int i = 0; i < n; i++)
{
LinkedList NewNode = (LinkedList)malloc(sizeof(Node));
NewNode->Data = rand() % 10;
NewNode->next = p->next;
p->next = NewNode;
}
return;
}
void showLinkedList(LinkedList L) {
int i = 1;
L = L->next;
while (L)
{
printf("第%d个节点=%dt",i,L->Data);
printf("地址=%xt", L);
printf("next指针=%xn", L->next);
++i;
L = L->next;
}
printf("n");
}
void test2() {
LinkedList L = (LinkedList)malloc(sizeof(Node));
L->next = NULL;/*创建一个带头节点的链表*/
CreatesqLinkList( &L, 5);//头部插入5个节点
showLinkedList(L);
InsertLinkedList(&L, 1, 12);/*在第2个位置插入元素12*/
printf("在第1个位置插入元素12n");
showLinkedList(L);
int rs;
DeleteLinkedList(&L,6,&rs);
printf("删除在第6个位置，删除的内容为：%dn",rs);
showLinkedList(L);
printf("尾插法创建整表n");
CreatBackpushLinkList(&L,5);
showLinkedList(L);
system("Pause");
}
int main() {
//test1();
test2();
}

头指针、头节点的异同
头指针：头指针用来标识链表，必须存在，一般指向头节点。
头结点：可有可无，一般头节点放在第一个节点前，用于统一对链表的插入和删除操作。数据域一般没有意义。
顺序存储和链式存储的优缺点
顺序存储用于很少插入和删除，但是频繁查询。
链式存储用于很少查询，但是频繁插入和删除的场合。且避免内存碎片问题。