首页 > GAME > 游戏 > 正文

台州帽闯旱商贸有限公司,怀化烫芬椒电子商务有限公司,新乡抛抛培训学校

纪太虚叹了口气,此时莲花佛祖头上的那道符文明灭不定:“张大人怎么如此的心急,以张大人的本事,过不了多久,这道符文就会毁去的!”纵然是纪太虚的符文能够克制六魂幡的力量,但是这也是要看法力的大小!水能灭火谁都知道,但是却也有杯水车薪的说法!

手机点击广告赚钱贴吧

“这个——”纪太虚缓缓说道:“我的那个徒弟,现在跟她勾搭上了——”
心里想起了刘皓和娜美的事情,在知道之后她心里可是酸酸的,没有妒忌,可是却十分的羡慕娜美,现在她也呆在这里刘皓的怀里了,想到刚才刘皓安慰自己的样子,最先发现自己的状况,那么的细心可雅的心脏好像藏着一只活蹦乱跳的小鹿一般,扑通扑通心跳加速跳动,浑身血液的流动速度都好像快了许多,整个人好想发烫似的。

不过刘皓就是不想主神那么快苏醒才没杀了赫尔巴,不然以他的速度不依不挠的追上去,迟早都能杀死赫尔巴的,毕竟现在赫尔巴不是以巅峰姿态逃走,而是被打得重伤逃跑,怎么可能逃得过刘皓。

Single linked list by cursor


有了指针实现看似已经足够了,那为什么还要有另外的实现方式呢?原因是诸如BASICFORTRAN等许多语言都不支持指针,如果需要链表而又不能使用指针,那么就必须使用另外的实现方法。还有一个原因,是在ACM-ICPC,OI等竞赛中,比赛时间有限,用指针写起来太费事,而且数量不多的情况下,用数组实现的脸变运行速度会更快。还有一些人觉得用指针写起来不优雅。嗯,不管怎么说,多掌握一种写法还是有必要的,说不定面试就会被问到2333

 

下面我会先把游标实现的细节阐述清楚,然后给出一个例题,来辅助理解。

 

其实游标在操作起来和普通链表并无太大不同,实际上两者的实现代码(特别是链表中函数的实现)差别不大,游标实现的链表效率会高一些,因为他是通过数组存储数据的,所以读写速度都是O(1)的,非常快。但是它并不能像普通链表一样实现动态增长缩减,一旦定义了数组大小,则能存储的数据的个数便不可更改了,所以更适合事先知道最大数据个数的案例

 

根据之前的知识,在链表的指针实现种有两个重要的特点

      • 数据存储在一组结构体中。每一个结构体包含有数据以及指向下一个结构体的指针。
      • 一个新的结构体可以通过调用malloc而从系统全局内存(global memory)得到,并可以通过调用free而被释放。

 

那游标法就必须能够模拟这两条特性,因为这是指针的基础性质。满足条件1的逻辑方法是要有一个全局的结构体数组,这个数组用来干嘛的?应该很容易想到——一方面存数据,这是单元内容。另一方面,那么下标呢?对于这个数组的任何单元,它的下标用来代表一个地址。

 

先给出一些声明

 1 typedef int PtrToNode;       //因为现在不需要把数据和指针绑定,所以不再是结构体,而是数组下标
 2 
 3 typedef PtrToNode List;
 4 
 5 typedef PtrToNode Position;
 6 
 7 #define SpaceSize 100
 8 
 9 struct Node{
10 
11     int Element;
12 
13     Position Next;
14 
15 };
16 
17  
18 
19 struct Node CursorSpace[SpaceSize];

 

这里的声明和之前的指针实现保持结构上的一致,这样就会形成一种对称的美感~

 

现在我们必须模拟条件2,让CursorSpace数组中的单元代行malloc和free的职能。为此,我们将保留一个数组(也就是free list),用slot命名,还挺形象2333,这个表由不在任何表中的单元构成。而且用0号单元作为表头,下面给出它的初始配置

 

Slot

Element 

Next

0

 

1

1

 

2

2

 

3

3

 

4

4

 

5

5

 

6

6

 

7

7

 

8

8

 

9

9

 

10

10

 

0

 这是一个初始化的CursorSpace,对于Next,0值等价于一个NULL指针。上面的状态用链表形式表示为:

CursorSpace[0]—>CursorSpace[1]—>CursorSpace[2]—>CursorSpace[3]—>CursorSpace[4]—>CursorSpace[5]—>CursorSpace[6]—>CursorSpace[7]—>CursorSpace[8]—>CursorSpace[9]—>CursorSpace[10]—>NULL.

 

而这个Slot的值,其实就是CursorSpace这个结构体数组的下标!!理解这点,下面的分配和返还函数的细节就容易理解了。

 

我们做什么操作都离不开第一步——初始化,这很简单,一个循环就够了。

与此同时,为了执行malloc的功能,需要把表头后面的第一个元素从freelist中删除,为什么要这样做——因为这个slot数组模拟的是系统内存,你申请一块,他就少一块。为了执行 free的功能,我们把要删除的单元放在freelist的前面,下面给出内存分配和返还的游标实现。如果没有可用空间,我们就让P=0,它表明没有空间可用,并且也可以使分配函数的第二行称为空操作。

 

先说初始化一个游标空间 

 1 void Initial(){
 2 
 3     int i;
 4 
 5     for (i=0; i<SpaceSize-1; i++)   //遍历每一个单元
 6 
 7         CursorSpace[i].Next=i+1;    //依次对next升序编号
 8 
 9     CursorSpace[0].Element=0;       //初始元素置空
10 
11     CursorSpace[SpaceSize-1].Next=0;//把最后一个单元的next设为0,就类似指针链表的尾指针是NULL
12 
13 }

 

下面这两个是重中之重各位要看仔细了这两个基础操作理解透彻了后面的都是小菜一碟。

 

 1 static Position CursorAlloc(){
 2 
 3     Position P;
 4 
 5     P=CursorSpace[0].Next;     //先从next的第0个单元获取一个数,这个数是第P个单元的地址
 6 
 7     CursorSpace[0].Next=CursorSpace[P].Next; //cursor 0后面本来接的是cursor P,但现在第P个单元被申请走了,所以顺接到P后面的位置。
 8 
 9     return P;
10 
11 }

 

这里的CursorSpace[0]仅代表一般意义上的“第一个元素”,未必是真正的下标0.这几句代码不太好理解,我一开始学的时候费了不少劲去弄懂,后来总结出一个状态转换的示意图,能很清晰地解释这个函数的运行过程:

 因为malloc的时候要将第一个元素(表头之后的第一个)从freelist中删除。

 

 释放内存:

1 void CursorFree(Position P){
2     CursorSpace[P].Next=CursorSpace[0].Next;//cursor P后面接上原本是cursor 0所指的下一个
3     CursorSpace[0].Next=P; //cursor 0后面接上被删除的P,相当于返还给操作系统。
4 }

 

这两句代码的顺序不能反过来,不然的话,cursor 0里面存的Next值就会改变,顺序就乱了。不过——我们思考这个free过程的时候最好从下往上看,因为要返还P这个单元,所以从逻辑上,表头的下一位记录P,然后P记录“原本是表头的下一位”那个单元的序号——也就是下标。记住!是从逻辑上,不是从代码细节上。实际写的时候要考虑边边角角,调整Next值的顺序一定要小心,就像用指针删除链表时的顺序问题(回想一下)。

 这个的运行过程如下:

 

 

因为free后要把该单元放在freelist的前端,放回去。

有没有发现,这两个函数的操作是完全对称的!多么和谐的美感啊,无论顺序和具体的步骤,他们都是对称的,所以这个细节也会有利于我们去理解内存的分配和返还机制。这或许对我们理解后续课程有帮助。

 

 

有了这些,链表的游标实现就简单了。为了前后一致我们将用一个头节点实现我们的链表。为了方便从整体架构上理解游标链表,给出一个例子:

Slot

Element

Next

0

-

6

1

B

9

2

F

0

3

Header

7

4

0

5

Header

10

6

-

4

7

C

8

8

D

2

9

E

0

10

A

1

假设L=5,M=3,那么L表示链表a->b->e->NULL,M表示链表c->d->f->NULL为了写出用游标实现链表的这些函数,必须传递和返回与指针实现时相同的参数。

 

这节因为有了之前的基础,注释就不写那么冗长了。

 

判断是否为空表,也就是一个元素都没有的表。

1  int Isempty(List L) {
2 
3       return CursorSpace[L].Next==0;
4 
5 }

 

判断是否为末尾

1 int IsLast(Position P) {
2 
3     return CursorSpace[P].Next==0;
4 
5 }

虽然细节和判空相同,但是用作接口由于实际功能有细微差别,还是要区分开写的。

 

查找是这样的

 1 Position Find(int X,List L) {
 2 
 3     Position P;
 4 
 5     P=CursorSpace[L].Next;
 6 
 7     while(P && CursorSpace[L].Element!=X)   //当后续的表还存在,并且还未找到给定的X时
 8 
 9         P=CursorSpace[P].Next;     //向后迭代,并逐个比对元素
10 
11     return P;       //返回X在L中的位置,当没有找到时,返回0
12 
13 }

 

 

我们再说删除:

和之前一样,删除要先找到前一个元素

 1 Position FindPrevious(int X,List L){
 2 
 3     Position P;
 4 
 5     P=L;
 6 
 7     while (P && CursorSpace[CursorSpace[P].Next].Element!=X) { //P没有走到末尾,同时还没找到给定的X时
 8 
 9       P=CursorSpace[P].Next; //P向后走
10 
11  }//走到这一步时,说明要么没找到,P=NULL(结尾处),要么找到了,P=前驱的位置
12 
13     return P;
14 
15 }

 

接下来就要删除了,有了前面的基础,就容易理解了。

 1 void Delete(int X , List L){
 2 
 3     Position P,TempCell;
 4 
 5     P=FindPrevious(X, L);
 6 
 7     if (!IsLast(P)) {
 8 
 9         TempCell=CursorSpace[P].Next;
10 
11         CursorSpace[P].Next=CursorSpace[TempCell].Next;//相当于P->Next=P->Next->Next
12 
13         CursorFree(TempCell);
14 
15     }
16 
17 }

 

 

再说插入

 

 1 void Insert(int X,Position P){
 2 
 3     Position TempCell;
 4 
 5     TempCell=CursorAlloc(); //申请一块新内存
 6 
 7     if(!TempCell)
 8        printf("Out of space!");    //这是为了增强程序的健壮性,给出错误提示(俗称打出GG)
 9 
10     CursorSpace[TempCell].Element=X;
11 
12     CursorSpace[TempCell].Next=CursorSpace[P].Next;
13 
14     CursorSpace[P].Next=TempCell;//这三行作用和用指针极其类似,对比着看吧
15 
16 }    

 

哦对了,应该有不少人对之前的“freelist”感到疑惑吧hhhhh   它从字面上看表示了一种有趣的数据结构,从freelist删除的单元是刚刚由free放在那里的单元。因此,最后被放在freelist的单元是最先被拿走的单元。有一种数据结构也具有这种性质,叫做栈(stack),它是下一节要讨论的内容。

 

 

 

下面给出一个有趣的题目,emmmm有兴趣的or有能力的可以继续往下看——没人希望自己很弱吧,所以都接着往下看吧哈哈哈

 

破损的键盘(又名:悲剧文本),Uva OJ  11988

        你有一个破损的键盘,键盘上的所有键都可以正常工作,但有时Home或者End键会自动按下。你并不知道键盘存在这一问题,于是专心地打稿子,甚至连显示器都没打开。当你打开显示器后,展现在你面前的是一段悲剧的文本。你的任务是打开显示器之前,计算出这段悲剧文本。

        输入包含多组数据,每组数据占一行,包含不超过100000个字母、下划线、字符“[”或者“]”。其中字符“[”表示Home键,“]”表示End键。输入结束标志为文件结束符(EOF)输入文件不超过5MB,对于每组数据,输出一行,即屏幕上的悲剧文本。

Sample:

 

Input

This_is_a_[Beiju]_text [[]][]Happy_Birthday_to_Tsinghua_University

 

Output

BeijuThis_is_a__text Happy_Birthday_to_Tsinghua_University

 

最简单的想法是用一个数组保存这段文本,然后用一个变量pos保存光标的位置。这样的话,输入一个字符相当于在数组中插入一个字符……那这就很尴尬了,每插入一个字符,需要把当前位置的所有元素向右移动,还要考虑是否存在溢出的问题。很不方便而且时间开销巨大,这样的代码妥妥TLE

 

解决方案是用链表,每输入一个字符就把它存起来。假设输入的字符串是s[1~n],则可以用next[i]表示在当前显示器中s[i]右边的字符编号——也就是对应的下标。方便起见,假设字符串s的最前面有一个虚拟的s[0],则next[0]就表示显示器中最左边的第一个有效字符。再用一个变量cur表示光标位置:当前光标位于s[cur]的右边。cur=0说明光标在虚拟字符的右边,也就是显示器的最左边、刚开始要输入的那个位置。

 

为了移动光标,还需要用一个变量last表示显示器的最后一个字符是s[last]。现在思路大概理顺了,实现如下:
 

 1 #include <stdio.h>
 2 
 3 #include <string.h>
 4 
 5 const int maxn = 100000+5;
 6 
 7 int last,cur,next[maxn],i;
 8 
 9 char s[maxn];
10 
11 int main(){
12 
13     while (scanf("%s",s+1)==1) {       //每次输入一个字符,存储地址向后偏移一位
14 
15         int n=strlen(s+1);          //n为当前字符串长度
16 
17         last=cur=0;
18 
19         next[0]=0;
20 
21         for (i=0; i<n+1; i++) {     //遍历每一个字符
22 
23             char ch=s[i];
24 
25             if(ch=="[") cur=0;      //遇到Home键就把光标移到最左边
26 
27             else if(ch=="]") cur=last;//遇到End键就把光标移到最后的位置
28 
29             else{               //如果是文本
30 
31                 next[i]=next[cur];
32 
33                 next[cur]=i;
34 
35                 if(cur==last)last=i;    //更新最后一个字符的编号
36 
37                 cur=i;          //移动光标
38 
39             }
40 
41         }
42 
43         for (i=next[0];i!=0 ;i=next[i])   //对于建立好的链表,通过next数组遍历整个处理后的字符串
44 
45             printf("%c",s[i]);
46 
47         printf("
");
48 
49     }
50 
51     return 0;
52 
53 }

有哪里感到疑惑的就直接写在评论里吧,我会积极参与讨论的2333

 

下一篇写栈。

 

 

 

当前文章:http://mabebox.com/array/c1cj3stj2m.html

发布时间:2019-01-17 02:04:53

现在什么网络游戏好玩好赚钱 最能挣钱的专业 没钱咋用电脑赚到钱 神器挂机赚钱 开花店赚钱不 一个月能赚一万的工作 哪种手机赚钱软件好 850游戏有人赢过钱吗

编辑:侯秉石


声明:所发布的内容均来源于互联网,目的在于传递信息,但不代表本站赞同其观点及立场,版权归属原作者,如有侵权请联系删除。
在农村做什么小本生意好

国外有哪些赚钱的平台

适合坐办公室的兼职