1. 首页
  2. 文章中心
  3. 数据结构与算法

《数据结构与算法分析》学习笔记（三）——链表ADT

90 阅读 0 评论
我是靠谱客的博主 单身嚓茶，这篇文章主要介绍《数据结构与算法分析》学习笔记（三）——链表ADT，现在分享给大家，希望可以做个参考。

今天简单学习了下链表，待后续，会附上一些简单经典的题目的解析作为学习的巩固

首先要了解链表，链表其实就是由一个个结点构成的，然后每一个结点含有一个数据域和一个指针域，数据域用来存放数据，而指针域则用来存放下一个结点的地址。

一、链表的基本知识

1、先给出结点的定义。

复制代码
1
2
3
4
5
6
7
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;struct Node
{
ElementType Element;
Position next;
};

 

2、下面就是一些常见的链表的操作

复制代码
1
2
3
4
5
6
7
8
9
10
11
List init(List L);
int IsEmpty(List L);
int IsLast(Position P,List L);
Position Find(ElementType X,List L);
void Delete(ElementType X,List L);
Position FindPrevious(ElementType X,List L);
void Insert(ElementType X,List L,Position P);
void DeleteList(List L);
Position Header(List L);
Position First(List L);
void Print(List L);

 

 

3、具体每个的分析啦

 

复制代码
1
2
3
4
5
List init(List L)
{
L=new struct Node;
L->next =nullptr;return L;
}

 

这个是初始化链表，链表默认有一个空的头指针，不用来存放数据，只是用来处理一些特殊的情况，个人认为一个结点的代接换取代码的简洁是很好的选择，

 

 

复制代码
1
2
3
4
int IsEmpty(List L)
{
return L->next==nullptr;
}

这个是判断链表是否为空。

 

 

 

 

Position Find(ElementType X,List L)

{

Position p;

p=L->next;

while (p!=nullptr&&p->Element!=X )

{

p=p->next;

}

  

return p;

}

由于链表跟指针不同，没有下标可以直接访问，所以我们需要一个个的遍历。

 

 

复制代码
1
2
3
4
5
int IsLast(Position P,List L)
{
Position p;
p=L->next;
if (p->next!=nullptr)
{
p=p->next;
}

return p==P;
}

 

判断是否是最后一个。

 

 

 

 

复制代码
1
2
3
4
5
6
7
8
9
10
11
void Delete(ElementType X,List L)
{
Position p,tempCell;
p=FindPrevious(X,L);
if(!IsLast(p,L))
{
tempCell=p->next;
p->next=tempCell->next;
delete tempCell;
}
}

删除的话重点是别忘记释放内存

 

 

 

 

 

复制代码
1
2
3
4
5
6
7
8
9
Position FindPrevious(ElementType X,List L)
{
Position p;
p=L;
while (p->next!=nullptr&&p->next->Element!=X)
{
p=p->next;
}return p;
}

与查找相关

 

 

复制代码
1
2
3
4
5
6
7
8
//Insert(after legal Position P)
void Insert(ElementType X,List L,Position P)
{
Position tempCell;
tempCell = new struct Node;


if (tempCell==nullptr)
{
cout<<("Out of space!!")<<endl;
}

tempCell->Element=X;
tempCell->next = P->next;
P->next=tempCell;
}

默认插入在结点的后面

 

 

 

 

复制代码
1
2
3
4
void DeleteList(List L)
{
Position p;
p=L->next;
L->next=nullptr;
while (p!=nullptr)
{


Position pTemp=p->next;
delete p;
p=pTemp;
}

}

清空链表

 

 

 

 

 

复制代码
1
2
3
4
5
6
void Print(List L)
{
Position p;
p=L->next;
while(p!=nullptr)
{
cout << p->Element.coe << p->Element.index <<" “;
p=p->next

}
cout<<endl;
}

 

打印链表

 

 

 

 

二、多项式的加法（减法是类似的）

1、首先应该确定Elementtype是什么，在此我定义了一个结构体，其中包括系数coe和指数index。

 

复制代码
1
2
3
4
typedef struct
{
float coe;
float index;}ElementType;

2、然后便是多项式加法的算法，首先默认多项式的系数是从小到大递增的。然后进行加法的时候，就用两个指针同时对两个链表进行遍历，碰到相同系数的就相加，不同的就直接加入到新链表中，然后记得相加为0的时候要进行删除。

 

代码如下：

 

复制代码
1
2
3
4
5
6
7
8
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
typedef struct
{
float coe;
float index;
}ElementType;
struct Node
{
ElementType Element;
Position next;

};

 

复制代码
1
2
3
4
5
6
7
8
//实现相应的函数的功能
List init(List L);
void Print(List L);
void initPolynomial(List L);
void hebing(List L);
void polyAdd(List L1,List L2,List L3);
void polySub(List L1,List L2,List L3);

void select(List L);



List init(List L)
{
L->next =nullptr;


return L;
}
void Print(List L)
{
Position p;
p=L->next;


while(p!=nullptr)
{
cout << p->Element.coe <<"X^"<< p->Element.index;
if(p->next!=nullptr&&p->Element.coe>0)
{
cout<<"+";
}
p=p->next;
}
cout<<endl;
}
void initPolynomial(List L)
{
DeleteList(L);


Position p,pre;
pre=L;
int coe,index;



while (1)
{
cout<<"Please scanf coe and index(以0 0退出）:";
cin>>coe>>index;


if(coe==0 && index==0)
{
break;
}
else
{
p=new struct Node;
p->Element.coe=coe;
p->Element.index=index;
p->next=nullptr;
pre->next=p;
pre=p;
}
}
hebing(L);


}


void hebing(List L)
{
Position pi,pj,pk2,pk1;
pi=L->next;
if(pi==nullptr||pi->next==nullptr)
{
return ;
}
for(pk1=L,pi=L->next;pi!=nullptr&&pi->next!=nullptr;pi=pi->next)
{
for(pj=pi->next,pk2=pi;pj!=nullptr;pj=pj->next)
{
if(pi->Element.index==pj->Element.index)
{
pi->Element.coe+=pj->Element.coe;
pk2->next=pj->next;
Position pTemp=pj;
delete pTemp;
pj=pk2;
}
pk2=pj;
}
if(pi->Element.coe==0)
{
pk1->next=pi->next;
Position pTemp=pi;
free(pTemp);
pi=pk1;
}
pk1=pi;
}
select(L);
}


void select(List L)
{
Position pi,pj;
pi=L->next;
if(pi==nullptr||pi->next==nullptr)
{
return ;
}


for(pi=L->next;pi->next!=nullptr;pi=pi->next)
{
Position ptemp=pi;
for(pj=pi->next;pj!=nullptr;pj=pj->next)
{
if(pj->Element.index<pi->Element.index)
{
ptemp=pj;
}
}


ElementType temp=ptemp->Element;
ptemp->Element=pi->Element;
pi->Element=temp;
}


}



void polySub(List L1,List L2,List L3)
{
Position p1=L1->next;
Position p2=L2->next;


Position p3=L3;


while (p1!=nullptr&&p2!=nullptr)
{
if(p1!=nullptr&&p2!=nullptr&&p1->Element.index==p2->Element.index)
{
Position p=new struct Node;
p->Element.index=p2->Element.index;
p->Element.coe=-p2->Element.coe+p1->Element.coe;
p->next=p3->next;
p3->next=p;
p3=p;


p1=p1->next;
p2=p2->next;


}



while(p1!=nullptr&&p2!=nullptr&&p1->Element.index>p2->Element.index)
{
Position p = new struct Node;
p->Element.index=p2->Element.index;
p->Element.coe=p2->Element.coe;
p->next=p3->next;
p3->next=p;
p3=p;


p2=p2->next;
}



while (p1!=nullptr&&p2!=nullptr&&p1->Element.index<p2->Element.index)
{
Position p = new struct Node;
p->Element.index=p1->Element.index;
p->Element.coe=p1->Element.coe;
p->next=p3->next;
p3->next=p;
p3=p;


p1=p1->next;
}


}
if(p1!=nullptr)
{
while(p1!=nullptr)
{
Position p = new struct Node;
p->Element.index=p1->Element.index;
p->Element.coe=p1->Element.coe;
p->next=p3->next;
p3->next=p;
p3=p;
p1=p1->next;
}
}
if(p2!=nullptr)
{
while(p2!=nullptr)
{
Position p = new struct Node;
p->Element.index=p2->Element.index;
p->Element.coe=-p2->Element.coe;
p->next=p3->next;
p3->next=p;
p3=p;


p2=p2->next;
}
}
hebing(L3);
}


void polyAdd(List L1,List L2,List L3)
{
Position p1=L1->next;
Position p2=L2->next;


Position p3=L3;


while (p1!=nullptr&&p2!=nullptr)
{
if(p1!=nullptr&&p2!=nullptr&&p1->Element.index==p2->Element.index)
{
Position p=new struct Node;
p->Element.index=p2->Element.index;
p->Element.coe=p2->Element.coe+p1->Element.coe;
p->next=p3->next;
p3->next=p;
p3=p;


p1=p1->next;
p2=p2->next;


}



while(p1!=nullptr&&p2!=nullptr&&p1->Element.index>p2->Element.index)
{
Position p = new struct Node;
p->Element.index=p2->Element.index;
p->Element.coe=p2->Element.coe;
p->next=p3->next;
p3->next=p;
p3=p;


p2=p2->next;
}



while (p1!=nullptr&&p2!=nullptr&&p1->Element.index<p2->Element.index)
{
Position p = new struct Node;
p->Element.index=p1->Element.index;
p->Element.coe=p1->Element.coe;
p->next=p3->next;
p3->next=p;
p3=p;


p1=p1->next;
}



}
if(p1!=nullptr)
{
while(p1!=nullptr)
{
Position p = new struct Node;
p->Element.index=p1->Element.index;
p->Element.coe=p1->Element.coe;
p->next=p3->next;
p3->next=p;
p3=p;
p1=p1->next;
}
}
if(p2!=nullptr)
{
while(p2!=nullptr)
{
Position p = new struct Node;
p->Element.index=p2->Element.index;
p->Element.coe=p2->Element.coe;
p->next=p3->next;
p3->next=p;
p3=p;


p2=p2->next;
}
}

}

3、桶式排序与基数排序

（1）桶式排序：假如有N哥整数，范围从1到M，我们可以创建一个数组Count，大小为M并初始化为0，于是，Count有M个桶，开始他们是空的，当i被读入的时候Count[i]增加1，在所有的输入都被读完以后，扫一遍数组Count，然后便可以打印出来排好序的表。

 

 

 

复制代码
1
2
3
    int A[1001];
memset((void *)A, 0, 1001*sizeof(int));      //初始化0；
int temp;
cout<<"Please scanf the numbers(数字在【1，1000】，以0退出）;"<<endl;
while(1)
{


cin>>temp;


if(temp<0||temp>1000)
{
cout<<"temp输入有误，该数已排除"<<endl;            //排除超限的数
cin>>temp;
}


if(temp==0)
{
break;                             //循环出口
}



A[temp]++;
}
for(int i=1;i<1001;i++)
{
if (A[i]!=0)
{
cout<<i<<"  ";             //打印处结果
}
}
cout<<endl;

return 0;

(2)基数排序

基数排序是对桶式排序的一种推广，由于桶式排序对空间的需求太高，所以我们考虑可以多次桶排序，降低M的值，就可以达到降低空间的需求，例如正整数的排序，我们可以把每一位都拆分出来，这样M的范围只有从0到9，也就是说我们一下子省去N多不必要的空间，碰到，有相同数的我们考虑接到这个i值下的链表即可。然后我COPY书上的图，让我们更好的理解

IMAG0174.jpg

 

最后贴出代码。

 

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
typedef struct Node
{
    int element;
    Node *next;
}Node;

typedef Node* pNode;


int main(int argc, const char * argv[])
{
    Node A[10];
    for(int i=0;i<10;i++)
    {
        A[i].next=nullptr;
    }
    int temp,Max=0;
    cout<<"请输入要进行排序的数(范围≥0,以-1退出)"<<endl;
    
    while(1)
    {
        cin>>temp;
        if(temp<-1)
        {
            cout<<temp<<"Scanf Error!"<<endl;
            cin>>temp;
        }
        if(temp==-1)
        {
            break;
        }
        
        if(temp>Max)
        {
            Max=temp;
        }
        
        int i=temp%10;
        auto node = new Node;
        node->element=temp;
        node->next=nullptr;
        
        pNode p= A+i;
        
        while (p->next!=nullptr)
        {
            p=p->next;
        }
        p->next=node;
    }
    
    int N=0;
    while (Max)
    {
        N++;
        Max/=10;
    }
    int n=1;
    int XX=1;
    while (n!=N+1)
    {
        XX*=10;
        for (int i=0; i<10; i++)
        {
            pNode p = (A+i)->next;
            pNode q = (A+i);
            while (p!=nullptr)
            {
                int temp=p->element/(XX)%10;
                if(temp==i)
                {
                    q=p;
                    p=p->next;
                    continue;
                }
                else
                {
                    q->next=p->next;
                    pNode ptemp=A+temp;
                    while(ptemp->next!=nullptr)
                    {
                        ptemp=ptemp->next;
                    }
                    p->next=nullptr;
                    ptemp->next=p;
                    p=q->next;
                    
                }
                
            }
            
        }
        n++;
    }
    
    
    
    
    
    
    for(int i=0;i<10;i++)
    {
        pNode p=A+i;
        p=p->next;
        while (p!=nullptr)
        {
            cout<<p->element<<"  ";
            p=p->next;
        }
        cout<<endl;
    }
    
    
    
    
    
    
    
    
    return 0;
}

 

 

 

 

 

 

最后

以上就是单身嚓茶最近收集整理的关于《数据结构与算法分析》学习笔记（三）——链表ADT的全部内容，更多相关《数据结构与算法分析》学习笔记（三）——链表ADT内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(60)

相关文章

POJ2540-Hotter Colder（半平面交）
POJ2540-Hotter Colder（半平面交）
深度学习——预备知识（1）数据操作1.一些基本的概念问题理解2.预备知识
深度学习——预备知识（1）数据操作1.一些基本的概念问题理解2.预备知识
《程序设计基础》学习总结 一、知识点二、 PTA总结 三、学习方法四、CSDN 五、学习阻力与克服方法六、未来java学习规划
《程序设计基础》学习总结 一、知识点二、 PTA总结 三、学习方法四、CSDN 五、学习阻力与克服方法六、未来java学习规划
Git push代码报错failed to push some refs to解决办法
Git push代码报错failed to push some refs to解决办法
《数据结构与算法分析》学习笔记（三）——链表ADT
《数据结构与算法分析》学习笔记（三）——链表ADT
数据结构教材中hash的使用及一些基本概念和方法
数据结构教材中hash的使用及一些基本概念和方法
关于Clifford A.Shaffer老师数据结构与算法分析中里用链表实现线性表的具体实现的感想
关于Clifford A.Shaffer老师数据结构与算法分析中里用链表实现线性表的具体实现的感想
如何解决error: failed to push some refs to 'git
如何解决error: failed to push some refs to 'git

评论列表共有 0 条评论

立即
投稿
返回
顶部