20210325
回顾 | 数据结构-线性表（五）
Table of Contents
回顾
恋词U1,U2,U3,U4复习
- publicize v.引起公众对..的注意；（尤指用广告）宣传
- humanity n.人类；人性；人道；人文学科
- humane adj.人道的
- paralysis n.麻痹；瘫痪；（活动、工作等）能力的完全丧失
- markedly adv.明显地，显著地
- marker n.标记；标志
- economic n.经济学
- ecology n.生态学
- indifferent adj.冷漠的；不关心的；不感兴趣的
- reserve v.保留
- abide v.停留，保持；
- informed adj.了解情况的；见多识广的
- ineffectual adj.无效果的；（指人）无能的
- reviewer n.评论家；审查者
- plead v.恳求；辩护；提出..为理由
- monopoly n.垄断；专卖；专利权
- render v.使变得，使成为；给予；提供
- entrenched adj.根深蒂固的
- discern v.认出；察觉出；辨明；分清
- press forward 加紧进行；决心继续；努力前进
- impressionable adj.（通常指年轻人）易受影响的
- designate v.指明；指定
- transplant v.器官移植；使迁移
- transparent adj.透明的；明晰的；易识破的
- set aside v.挑出；拨出；留出；不理会
- ideology n.意识形态，（政治或社会的）思想意识，思想体系
顺序表操作复习
数据结构-线性表-建表（五）
顺序表建表算法代码
int A [maxSize]; //数组的最大长度。对应数组如果是其他类型，把int换掉即可。
int length; //严格来说要定义成无符号整型更好，即unsighed int。
int createList(int A[], int &length) //int A[],当数组这种写法定义成函数参数即对数组本身进行操作，相当于引用型
{
cin >> length; //希望建的表有多长，通过键盘输入。
if(length > maxSize) //输入顺序表长度肯定不可以大于maxSize，会发生溢出
return 0; //建表失败，返回0作为标记
fot(int i = 0; i < length; ++i) //从0开始到length-1存元素，i的最大值为length-1
cin >> A[i]; //逐个从键盘输入元素
return 1; //建表成功，返回1
}
单链表建表算法代码（尾插法）
就是一系列的插入操作，这里假设内存无限，这里指含有头结点的链表
void createLinkListR(LNode *&head) //指针要在函数内发生变化，故使用指针型引用型变量
{
head = (LNode*)malloc(sizeof(LNode)); //“搞个头出来”
head->next = NULL; //每次为链表申请一个结点空间的时候，把他的next指针设置为NULL是好的习惯。
LNode *p = NULL, *r = NULL; //p指针为接收新结点的指针，r为始终指向当前尾部结点的指针。
int n; //描述你要建的链表中的数据结点个数
std :: cin >> n; //不加using namespace才要加std ::
for(int i = 0; i < n; ++i) //在每一次循环内建一个新的结点并从键盘中输入一个数据传给新结点的data域
{
p = (LNode*)malloc(sizeof(LNode)); //“搞个新结点出来”，并用p指针指向它
p->next = NULL; //把他的next指针设置为NULL是好的习惯。
std :: cin >> p->data; //从键盘中输入一个数据并传入当前结点的data域内
p->next = r->next; //插入操作（这可以删掉，这里只是等价于在链表中部插入结点）
r->next = p //连接链表
r = p; //对r指针进行维护，让他始终指向当前最新的尾结点
}
}
单链表建表算法代码（头插法）
void createLinkListH(LNode *&head) //指针要在函数内发生变化，故使用指针型引用型变量
{
head = (LNode*)malloc(sizeof(LNode)); //“搞个头出来”
head->next = NULL; //每次为链表申请一个结点空间的时候，把他的next指针设置为NULL是好的习惯。
LNode *p = NULL; //由于我们每次都在头结点之后插入一个新的数据结点，就不需要标记尾结点的位置了，即r不需要了
int n; //描述你要建的链表中的数据结点个数
std :: cin >> n; //不加using namespace才要加std ::
for(int i = 0; i < n; ++i) //在每一次循环内建一个新的结点并从键盘中输入一个数据传给新结点的data域
{
p = (LNode*)malloc(sizeof(LNode)); //“搞个新结点出来”，并用p指针指向它
p->next = NULL; //把他的next指针设置为NULL是好的习惯。
std :: cin >> p->data; //从键盘中输入一个数据并传入当前结点的data域内
p->next = head->next;
head->next = p //连接链表
}
}
真题
键盘输入n个英文字母，输入格式为n、C1、C2...Cn，其中n表示为字母的个数，请编程以这些输入数据建立一个单链表，并要求将字母不重复的存入链表。
思路：输入一个数据。扫描其在链表中是否出现，如果出现，就什么都不做。否则，根据这个数据构造结点插入链表中。
void createLinkNoSameElem(LNode *&head)
{
head = (LNode*)malloc(sizeof(LNode));
head->next = NULL;
LNode *p;
int n;
char ch;
std :: cin >> n;
for(int i = 0; i < n; ++i)
{
std :: cin >> ch;
p = head->next;
while(p != NULL)
{
if(p->data == ch)
break;
p = p->next;
}
if (p == NULL)
{
p = (LNode*)malloc(sizeof(LNode));
p->data = ch;
p->next = head->next;
head->next = p;
}
}
}
结合图解理解：
视频：