C语言数据结构复习（1-2章）

2023-10-25 14:28:40

基础概念

1.数据元素：是数据的基本单位。一个数据元素由若干数据项组成，数据项是数据不可分割的最小单位。

2.数据类型：是性质相同的数据元素的集合及在这个集合上的一组操作。

3.数据结构

a、广义：按某种逻辑关系组织起来的一批数据应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。

数据结构包含三个方面的内容，即数据的逻辑结构、存储结构和对数据所施加的运算（操作），具体如下图所示。

数据的逻辑结构是从逻辑关系上描述数据的，是数据本身所固有的，与数据的储存无关，是独立于计算机的。

数据的存储结构是逻辑结构用计算机语言的实现，依赖于计算机。

数据的运算定义在逻辑结构上，并在储存结构上实现。

最常用的运算有查询，插入，删除，编辑，排序等

b、狭义：就是指数据的组织形式，即逻辑结构（具体4类：集合、线性结构、树形结构和图形结构）。

(1)集合:结构中的数据元素之间除了仅仅同属于一个集合外,不存在其他关系。
(2)线性结构:数据元素之间存在一对一的关系,即元素之间有先后关系。
(3)树形结构:数据元素之间存在一对多的关系,即元素之间有层次关系。
(4)图状结构或网状结构:数据元素之间存在多对多的关系,即任意两个元素之间都
可能有关系

4.算法

（1）定义：算法是由若干条指令组成的有限序列，是对特定问题求解步骤的一种描述

（2）算法原则：

1 有穷性一个算法必须总是在执行有穷步之后结束,且每一步都在有穷的时间内完成。

2 确定性算法中每一条指令都必须有确切的含义,无二义性。

3 可行性一个算法是可行的,是指算法描述的操作都是可以通过已经实现的基本
运算执行有限次来实现的,即一个算法必须在有限的时间内完成。

4 输入一个算法有零个或多个输入,作为算法加工的对象。

5 输出一个算法有一个或多个输出,这些输出往往同输入有着某些特定的关系。

（3）算法和程序的区别

算法必须是有穷的，而一个程序不一定满足有穷性。

程序中的指令必须是机器可以执行的，而算法中的指令无此限制。

一个算法如果能用机器可执行语言书写，那它就是一个程序。

（4）算法时间复杂度和空间复杂度的分析

假设执行每条语句所需的时间都为单位时间，则一个算法的时间耗费就是改算法中所有语句的频度之和即时间频度( T（n）)。

算法求解问题的输入量称为问题的规模（或大小）。

若有某个辅助函数f(n)

记作T(n)=O(f(n))

则称O（f(n)）为算法的渐进时间复杂度，简称时间复杂度

例：若T（n）=n（n+1）/2 则有所以时间复杂度为

推论（不扯推出的过程，公式难打）

当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

（5）算法分析

目的：分析算法的效率以求改进

主要方面：空间复杂性和时间复杂性

线性表

（1）定义：线性表是由n(n>=0)个数据元素（节点）,a1,a2......an组成的有限序列

(2) 特点：

(1)有且仅有一个节点(a1)没有直接前趋,称它为开始节点。
(2)有且仅有一个节点(an)没有直接后继,称它为终端节点。
(3)除开始节点外,线性表中其他任一节点a(2≤i≤n)都有且仅有一个直接前趋ai-1
(4)除终端节点外,线性表中其他任一节点a(1≤i≤n-1)都有且仅有一个直接后继算法中的ai+1

顺序表

1.顺序表是一种随机存取的结构。

2.特点：逻辑上相邻的节点其物理位置也相邻。

3.顺序表的定义方式：

顺序表节点的定义

文中代码需要重新在英语模式下输入才可运行，因为这是扫描上来的文本

typedef int ElemType;                 //线性表中数据类型

#define MAXSIZE 1024                 //线性表最大长度设置

typedef struct{                 
ElemType elem[MAXSIZE];             //线性表是向量储存，第一结点是elem[0]
int length;                        //表长
}SqList;

定义顺序表(两种方式)

SqList L;

其中,L表示由一维数组elem和长度 length组成的顺序表,L中第i个节点表示为L.elem[i-1],L的长度表示为L.length

SqList *L;

L为指向由一维数组elem和长度 length组成的 SqList顺序表类型的指针,L中第i个节点表示elem[i-1]或(*L).elem[i-1],长度表示为L->length或者(*L).length.

4.顺序表基本操作

初始化

把表长置为0即可

void InitList(SqList *L){

L->length=0;                      //空表,长度为0

}

定位（按值查找）

int Locate (SqList L, ElemType item){
 int i;

 for(i=0;i<L.length; i++)
 {
 if(L.elem[i]==item)
 return (i+1);
 }

 printf("找不到该值!");
 return FALSE;
}

插入

由于节点的物理顺序必须和节点的逻辑顺序保持一致，因此需要将插入位置后的所有元素向后移动一个储存空间，空出插入位置的储存空间。仅当插入在末尾时可以直接插入。

int Insert (SqList *L, int i, ElemType e)     //将新节点e插入顺序表L的第1个位置上
{
int j;
if(L->length==MAXSIZE){
printf("表满，溢出!");
return false;
}
else if(i<1||i>L->length){
printf("插入位置不合法!");
return false;
}
else{
for(j=L->length-1;j>=i-1;j--)
    L->elem[j+1]=L->elem[j];
L->elem[i-1]=e;
L->length++;
return true;
}


}

删除

删除原理与插入基本相同，只是删除的位置可以直接用后面的元素进行覆盖。将表长减去1即可

5顺序表的优缺点

优点：

(1)无需为表示节点间的逻辑关系而增加额外的存储空间。
(2)可以方便地随机存取表中任一节点。

缺点:

(1)插入或删除运算不方便,除表尾的位置外,在表的其他位置上进行插入或删除操作时都必须移动大量的节点,其效率较低。
(2)由于顺序表要求占用连续的存储空间存储分配只能预先进行(静态分配)。因此,
当表长变化较大时,难以确定合适的存储规模。若按可能达到的最长度预先分配表空间,
则可能造成一部分空间长期空置而得不到充分利用:若事先对表长估计不足,则插入操作
可能使表长超过预先分配的空间而造成溢出。

单链表

1.单链表的节点结构：

data

next

data为数据域，用于存放节点的值。next是指针域（链域），用来存放节点的直接后继的地址。

节点只有一个链域的链表称为单链表。

2.单链表的定义：

typedef int ElemType;
typedef struct LNode/节点类型定义
{
    ElemType data;
    struct LNode *next;
} LNode,*LinkList;

LNode x; //x是一个结构体节点变量
LinkList L,p;      //L、p是结构体指针变量，另一种写法LNode *L,*p;

在进行单链表操作时，我们经常会需要用到一个临时节点，由于这个节点是在我们需要时才产生的，所以成为动态节点变量。可通过标准函数生成

p=（LinkList）malloc(sizeof(LNode));

当使用完成后，不在需要它时，通过标准函数free()释放节点变量空间

free(p);

3.单链表的建立

尾插法建立单链表


void CreateListR(LinkList L)
{
int x;
LinkList P;
L=(LinkList)malloc(sizeof(LNode));
p=L;
scanf("%d",&x);
while(x!=-999)
{
p->next=(LinkList)malloc(sizeof(LNode));
p=p->next;
p->data=x: 
scanf("d",&x);
}
p->next=NULL;
}

头插法建立单链表

void CreateListF (LinkList L)
{
int x;
LinkList s;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
scanf("%d", &x);
while(x!=-999)
{
s=(LinkList)malloc(sizeof(LNode));
s->data=x;
s->next=L->next; 
L->next=s;
scanf("%d",&x);
}
}

4.单链表按值查找

LinkList Locate(LinkList L,ElemType item)//查找值为item的节点
{
    LinkList p;
    p=L->next;
    while(p&&p->data!=item)
        p=p->next;
    if(!p)
        return NULL;
    else
        return(p); 

}

平均时间复杂度O(n)

5.插入与删除

插入

int Insert(LinkList L,int i,ElemType item)//在单链表L上第i个节点前插入元素item
{
    LinkList p,s;
    p=L;
    int j=0;
    while(p&&j<i-1)
    {
        p=p->next;
        ++j; 
    }
    if(!p||j>i-1)
        return false;
    s=(LinkList)malloc(sizeof(LNode));
    s->data=item;
    s->next=p->next;
    p->next=s;
    return true;

}

删除

int Delete(LinkList L,int i)//在单链表L中删除p节点本身
{
    LinkList p,q;
    int j;
    q=L;
    j=0;
    while(q&&j<i-1)
    {
        q=q->next;
        ++j;
    }    

    if(!q||j>i-1)
    {
        return false;
    }
    p=q->next;
    q->next=p->next;
    free(p);
    return true;

}

码农公寓

基础概念

线性表

相关文章