数据结构笔记（c++）

       大二上学数据结构方法：20min理解概念+30min写代码（考伪代码手写，不能用vector库）+20min刷课后题；考试考：选择题+应用题+代码题。学完能：应付考试，写代码知道用什么容器，知道程序为什么慢，会手写底层代码，懂内部原理（干活用库，考试造库）。

        知识点看书做笔记，思维导图上网搜，错题及时回顾，下面是作业代码。（c++版,除了能运行的代码外其余为c,c++混用的伪代码）

一、线性表

1、顺序表（随机存取结构，占用连续存储空间，静态分配）

1）顺序表定义

//简洁定义
int A[maxSize];//顺序表为整形
int n;//长度为n
//结构体定义
typedef struct{
int data[maxSize];
int length;
}SqList;

2)初始化

void InitList(SqList &L){
L.length=0;
}

3）顺序表查找

返回下标：

int LocatedElem(SqList L,int e){
int i;
for(i=1;i<=L.length;i++){
if(e==L.data)return i;
return 0;
}

返回元素：

int GetElem(SqList L,int p,int &e){
if(p<1||p>L.length)return 0;
e=L.data[p];
return 1;
}

4)顺序表插入

int ListInsert(SqList &L,int p,int e){
int i;
if(p<1||p>L.length+1||L.length==maxSize-1)return 0;
for(i=L.length;i>=p;i–){
L.data[i+1]=L.data[i];
}
L.data[p]=e;
L.length++;
return 1;
}

5)顺序表删除

int ListDelete(SqList &L,int p,int &e){
int i;
if(p<1||p>L.length)return 0;
e=L.data[p];
for(i=p;i<L.length;i++){
L.data[i]=L.data[i+1];
}
L.length–;
return 1;
}

6)顺序表修改

int ListModify(SqList &L,int p,int x){
if(p<1||p>=L.length)return 0;
L.data[p]=x;
return 1;
}

能运行的代码：

#include <bits/stdc++.h>
#include<windows.h>
using namespace std;
#define maxSize 100
typedef int ElemType;
//顺序表定义
typedef struct{
int data[maxSize];
int length;
}SqList;
//顺序表初始化
void InitList(SqList &L){
L.length=0;
}
//顺序表插入
int ListInsert(SqList &L,int p,int e){
int i;
if(p<1||p>L.length+1||L.length>=maxSize-1)return 0;
for(i=L.length;i>=p;i–){
L.data[i+1]=L.data[i];
}
L.data[p]=e;
L.length++;
return 1;
}
//顺序表删除
int ListDelete(SqList &L,int p,int &e){
int i;
if(p<1||p>L.length)return 0;
e=L.data[p];
for(i=p;i<L.length;i++){
L.data[i]=L.data[i+1];
}
L.length–;
return 1;
}
//顺序表修改
int ListModify(SqList &L,int p,int x){
if(p<1||p>L.length)return 0;
L.data[p]=x;
return 1;
}
//打印顺序表
void PrintList(SqList L){
for(int i=1;i<=L.length;i++){
cout<<L.data[i]<<" ";
}
cout<<endl;
}
int main(){
SetConsoleOutputCP(65001);
SqList L;
InitList(L);
int op;
int pos,val,e;
while(true){
cout<<"\\n====菜单===="<<endl;
cout<<"1 插入\\n2 删除\\n3 修改\\n4 打印\\n0 退出"<<endl;
cout<<"请输入操作号：";
cin>>op;
if(op==0){
cout<<"程序结束"<<endl;
break;
}
else if(op==1){
cout<<"输入插入位置(从1开始)和数值:"<<endl;
cin>>pos>>val;
if(ListInsert(L,pos,val)){
cout<<"插入成功\\n";
}else{
cout<<"插入失效，位置非法\\n";
}
}
else if(op==2){
cout<<"输入要删除的位置：";
cin>>pos;
if(ListDelete(L,pos,e)){
cout<<"删除成功\\n";
}else{
cout<<"删除失败，位置非法\\n";
}
}
else if(op==3){
cout<<"输入修改的位置和新数值：";
cin>>pos>>val;
if(ListModify(L,pos,val)){
cout<<"修改成功";
}else{
cout<<"修改失败，位置非法\\n";
}
}
else if(op==4){
cout<<"当前顺序表：";
PrintList(L);
}
else{
cout<<"输入错误，重新选:)";
}
}
return 0;
}

2、单链表（顺序存储结构，不支持随机访问，动态分配）

1）单链表结点定义

typedef struct LNode{
int data;//数据域
struct LNode *next;//指针域
}LNode;

2）单链表初始化(408要用malloc，就不用new了)

int InitList(LNode *&L){
L=(LNode *)malloc(sizeof(LNode));
if(L==NULL)return 0;
L->next=NULL;
return 1;
}

3)单链表查找

按位查找：

int GetElem(LNode *L,int i,int &e){
if(i<1)return 0;
LNode *p=L->next;
int j=1;
while(p!=NULL&&j<i){
p=p->next;
j=j+1;
}
if(p==NULL)return 0;
e=p->data;
return 1;
}

按值查找：

int LocatedElem(LNode *L,int x){
LNode *p=L->next;
int j=1;
while(p!=NULL&&p->data!=x){
p=p->next;
j++;
}
if(p==NULL)return 0;
return j;
}

4)单链表插入

按位插入：

int ListInsert(LNode *&L,int i,int e){
LNode *p=L:
int j=0;
while(p!=nullptr&&j<i-1){
p=p->next;
j++;
}
if(p==nullptr)return 0;
LNode *s =(LNode *)malloc(sizeof(LNode());
s->data=e;
s->next=p->next;
p->next=s;
return 1;
}

头front插法：（链表都有头结点）

void CreatListF(LNode *&C,int a[],int n){
LNode *s;
int i;
C=(LNode *)malloc(sizeof(LNode));
C->next=NULL;
for(i=1;i<=n;i++){
s=(LNode *)malloc(sizeof(LNode));
s->data=a[i];
//关键步骤
s->next=C->next;
C->next=s;
}
}

尾rear插法：

void CreatListR(LNode *&C,int a[],int n){
LNode *s,*r;
int i;
C=(LNode *)malloc(sizeof(LNode());
C->next=NULL;
r=C;
for(i=1;i<=n;i++){
s=(LNode *)malloc(sizeof(LNode));
s->data=a[i];
r->next=s;
r=r->next;
}
r->next=NULL;
}

5)单链表删除

按位删除：

int ListDelete(LNode *&L,int i,int &e){
if(L==NULL)return 0;
if(i<1)return 0;
LNode *p=L:
int j=0;
while(p!=NULL&&j<i-1){
P=P->next;
j++;
}
if(p==NULL||p->next==NULL)return 0;
LNode *q=p->next;
e=q->data;
p->next=q->next;
free(q);
return 1;
}

按值删除：

int ListDeleteByVal(LNode *&L,int x,int &e){
LNode *p=L:
while(p->next!=NULL&&p->next->data!=x){
p=p->next;
}
if(p->next==NULL)return 0;
LNode *q=p->next;
e=q->data;
p->next=q->next;
free(q);
return 1;
}

6)单链表修改

int ListModify(LNode L,int x){
LNode *p;
p=L->next;
j=1;
while(p!=NULL&&j<i){
p=p->next;
j=j+1;
}
if(p==NULL)return 0;
p->data=x;
return 1;
}

能运行的代码：

#include<bits/stdc++.h>
using namespace std;
typedef struct LNode{
int data;
struct LNode *next;
}LNode,*LinkList;

int InitList(LinkList &L){
//L=(LNode *)malloc(sizeof(LNode));
L=new LNode;
if(L==NULL)return 0;
L->next=NULL;
return 1;
}

int ListInsert(LinkList &L,int i,int e){
LNode *p=L;
int j=0;
while(p!=NULL&& j<i-1){
p=p->next;
j++;
}
if(p==NULL)return 0;
LNode *s=new LNode;
s->data=e;
s->next=p->next;
p->next=s;
return 1;
}

int ListDelete(LinkList &L,int i,int &e){
if(L==NULL)return 0;
if(i<1)return 0;
LNode *p=L;
int j=0;
while(p!=NULL&&j<i-1){
p=p->next;
j++;
}
if(p==NULL||p->next==NULL)return 0;
LNode *q=p->next;
e=q->data;
p->next=q->next;
delete q;
return 1;
}

int ListModify(LinkList L,int i,int x){
LNode *p;
p=L->next;
int j=1;
while(p!=NULL&&j<i){
p=p->next;
j++;
}
if(p==NULL)return 0;
p->data=x;
return 1;
}
//遍历打印
void ListTraverse(LinkList L){
LNode *p=L->next;
while(p!=NULL){
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
//销毁链表，释放全部内存
void DestroyList(LinkList &L){
LNode *p;
while(L!=NULL){
p=L;
L=L->next;
delete p;
}
}
int main(){
LinkList L;
InitList(L);

ListInsert(L,1,1);
ListInsert(L,2,2);
ListInsert(L,3,3);
cout<<"插入之后：";
ListTraverse(L);

ListModify(L,2,99);
cout<<"修改第二位为99:";
ListTraverse(L);

int del_e;
ListDelete(L,1,del_e);
cout<<"删除第一位，删除值="<<del_e<<":";
ListTraverse(L);

DestroyList(L);
return 0;
}