《c语言数据结构补充（C language data structure supplement）.doc》由会员分享，可在线阅读，更多相关《c语言数据结构补充（C language data structure supplement）.doc（33页珍藏版）》请在三一文库上搜索。
1、c语言数据结构补充（C language data structure supplement）For Many a little make a mickle. progress every day.I. Basic Concepts and terminologyData (Data): a symbolic representation of informationIn computer science, a general term for all symbols that can be entered into a computer and processed by a computer
2、 programData element (Data Element): the basic unit of dataIn computer programs, usually considered and handled as a wholeA data element can consist of several data itemsA data item is the smallest unit of data that cannot be dividedData object (Data Object): a collection of data elements of the sam
3、e natureIs a subset of the dataStructure (Data): a collection of data elements that exist in one or more specific relationships with each otherThe data structure is divided into logical structure and physical structureThe relation between data is called logical structureThey are usually divided into
4、 four categories:* data elements in a collection structure, except that they belong to one typeNothing else* there is a one to one relationship between the data elements in the linear structure* there is a one to many relationship between data elements in tree structured structures* there are many t
5、o many relationships between data elements in graphs, structures, or mesh structuresThe data structure is formally defined as: the data structure is a two tuple: Data-Structure= (DS)Where: D is a finite set of data elementsS is a finite set of relations on DThe data structure of the complex number i
6、s defined as follows: Complex= (CR)Where: C is the two sets of real numbers C1C2Representing the real and imaginary parts of the complex number, respectivelyR=PP is a relation defined on a collection C1C2.The representation of data structures in a computer is called the physical structure of dataAls
7、o known as storage structureData structures have two different representations in a computer: sequential and non sequential representationsTwo different storage structures are obtained: sequential storage structure and chain storage structure* sequential storage structure: the logical relation betwe
8、en data elements represented by the relative positions of data elements in memory* chained storage structure: adds a pointer to the address in each of the data elementsUse this pointer to represent logical relationships between data elementsData type (Data Type): in a programming languageThe type of
9、 data that a variable hasIn C language, data types: base types and construction typesBasic types: integer, floating point, and character typeStructural types: arrays, structures, unions, pointers, enumerations, and customizationsTwo, linear tableLinear table (Linear List): n (n = 0) data elements (n
10、odes) A1A2A finite sequence consisting of anThe number of data elements n is defined as the length of the tableWhen n=0 is called an empty tableThe non empty linear table (n0) is often denoted as: (A1A2An).An example of 1 or 26 letters of alphabet (ABC,., Z)Example 2. Changes in the amount of comput
11、er ownership of a school from 1978 to 1983(6SeventeenTwenty-eightFiftyNinety-two188)Example 3 student health registration form is as followsFull nameStudent numberSexAgeHealthWangSeven hundred and ninety thousand six hundred and thirty-onemaleEighteenHealthyChen HongSeven hundred and ninety thousand
12、 six hundred and thirty-twofemaleTwentycommonlyLiu jianping1Seven hundred and ninety thousand six hundred and thirty-threemaleTwenty-oneHealthyZhangliliSeven hundred and ninety thousand six hundred and thirty-fourmaleSeventeenNeurasthenia2.1 order tableThe nodes of the linear table are stored in log
13、ical order sequentially in a set of address contiguous storage unitsA linear table stored in this method; referred to as a list of tablesIt is assumed that each element of the linear table needs to occupy l storage cellsThe storage location of the first unit is used as the storage location of the da
14、ta elementThe linear table in the i+1 data elements storage location for the LOC (ai+1) and the storage location for the LOC I data elements (AI) between satisfying the following relation: LOC (ai+1) =LOC (AI) +l the I storage location data elements linear table AI: LOC (AI (A1) =LOC) + (i-1) *lSinc
15、e the one-dimensional array in the C language is also expressed in sequential storageYou can use array types to describe sequential tablesBecause besides storing elements of a linear table with arraysThe order table should also use a variable to represent the length attribute of a linear tableSo we
16、define sequence table types with structure types# define ListSize 100Typedef int DataType;Typedef strucDataType dataListSize;Int length; Sqlist;In the sequential table storage structureIt is easy to implement some operations of the linear tableSuch as the construction of linear tables, elements of t
17、he first IVisitLinear table insert operations are defined in section I table (I = 1 n+1 positionInsert a new node xA linear table with a length of n (A1. a I-1AI.An) a linear table of length n+1 (A1. a I-1XAI.An)Linear table insertion algorithm: Void InsertList (Sqlist* L)DataType xInt i)int j;If (i
18、l.length+1 |)Printf (Position error); return ERROR;If (l.length=ListSize)Printf (overflow); exit (overflow);For (j=l.length-1; j=i-1; j-)L.dataj+1=l.dataj;L.datai-1=x;L.length+;Linear table deletion algorithm: Void deleteList (Sqlist* L)Int i)int j;If (il.length |)Printf (Position error); return ERR
19、ORFor (j=i; jdata=ch;P-next=head;Head=p;Ch=getchar ()Return (head)Tail insertion method: this method inserts the new node into the end of the current listTo do this, you have to add a trailing pointer, RSo that it always points to the tail node of the current listTail insertion algorithm, linklist,
20、creater ()char ch; listnode *p*r*head;Head=NULL; r=NULL;While (ch=getchar () = , n) P= (listnode *) malloc (sizeof (listnode);P-data=ch;If (head=NULL) head=p;Else r-next=p;R=p;If (R, =NULL) r-next=NULL;Return (head)Explanation: the first generated node is the start nodeInserts the start node into th
21、e empty tableIs inserted in the first position of the current listThe insertion operation on this location is different from the insertion operation in other locations in the listThe reason is that the location of the start node is stored in the head pointer (pointer variable), while the rest of the
22、 node is in the pointer domain of its predecessor nodeThe first if statement in the algorithm is used to do special processing for the insertion operation on the first positionThe second if statements in the algorithm are designed to deal with two different situations: empty tables and non empty tab
23、lesIf the first character read is the end of the symbolThe linked list head is an empty tableThe tail pointer R is also nullThe node *r does not exist; otherwise, the list head is not emptyThe last node *r is the terminal nodeThe pointer field should be emptyIf we add a node before the start node of
24、 the listCall it the head nodeThen there are two advantages: A, because the location of the start node is stored in the pointer field of the header nodeSo the operation in the first position of the list is consistent with the operation on the other location of the tableNo special handling is necessa
25、ry; B, regardless of whether the list is emptyThe head pointer refers to the head node in the non null pointer (pointer field empty head node table is empty)Therefore, the processing of empty tables and non empty tables is unifiedLinklist, createlistr1 () Char ch;Listnode *head= (LinkList) malloc (s
26、izeof (listnode);Listnode *p*rR=head;While (ch=getchar () = = n P= (listnode*) malloc (sizeof (listnode);P-data=ch;P-next=p;R=p;R-next=NULL;Return (head)2.2.3 search operation1, according to the serial number to findIn the listEven knowing the ordinal number of the visited node, INor can you access
27、nodes directly in ordinal numbers like IYou can only start with the head pointer of the listThe CIS domain next searches one node at a timeUntil the search to the first I nodethereforeA linked list is not a random access structureSet a single chain table length of nTo find the first I node in the ta
28、bleOnly when I = 1 nThe value of I is legalBut sometimes you need to change the position of the nodesSo we think of head nodes as zeroth nodesIts algorithm is as follows:Listnode * getNode (listnode* head)Int i)int j;Listnode * p;P=head; j=0;While (p-next jnext;J+;If (i=j) return p;Else return NULL;
29、2, by value searchLookup by value is in the listFind the node that has a node value equal to the given value keyIf soReturns the storage location of the node whose first value is key; otherwise returns NULLThe lookup process starts at the start nodeFollow the list by comparing the value of the node
30、with the given value keyIts algorithm is as follows:Listnode * locatenode (LinkList head)Int key)listnode * p=head-next;While (P =key & & p-data!)P=p-next;Return p;2.2.4 insertion operationThe insertion operation inserts a new node with the value of X into the I node of the tableThat is inserted bet
31、ween AI-1 and AIthereforeWe must first find the storage location of AI-1 pA data domain is then generated as a new node for XAnd the pointer field of node *p points to the new nodeThe pointer field of the new node points to node AITo achieve the three node AI-1A change in the logical relationship be
32、tween X and AIInsert process such as:Void insertnode (LinkList head)Datetype xInt i)listnode * P*q;P = getnode（头I-1）；如果（P = = null）误差（位置误差）；Q =（思路：*）malloc（sizeof（思路：）；q =数据= x；下一步；p =下一个q；2.2.5删除运算我个结点删去删除运算是将表的第因为在单链表中结点AI的存储地址是在其直接前趋结点一I-1的指针域下中所以我们必须首先找到一I-1的存储位置P然后令P -下一指向AI的直接后继结点即把AI从链上摘下最后释放
33、结点AI的空间将其归还给”存储池”无效deletelist（链表的头int i）思路：p* R；P = getnode（头I-1）；如果（P = = null | | P 下= = null）返回错误；下一步；下一步；自由（R）；从上面的讨论可以看出链表上实现插入和删除运算无须移动结点仅需修改指针三、循环链表循环链表时一种头尾相接的链表其特点是无须增加存储量仅对表的链接方式稍作改变即可使得表处理更加方便灵活单循环链表：在单链表中将终端结点的指针域空改为指向表头结点的或开始结点就得到了单链形式的循环链表并简单称为单循环链表为了使空表和非空表的处理一致循环链表中也可设置一个头结点这样空循环链表仅有
34、一个自成循环的头结点表示如下图所示：双向链表（双链表）：在单链表的每个结点里再增加一个指向其直接前趋的指针域之前这样就形成的链表中有两个方向不同的链故称为双向链表形式描述为：dlistnode typedef struct数据类型；结构dlistnode *之前*下； dlistnode；typedef dlistnode * dlinklist；dlinklist头；和单链表类似双链表一般也是由头指针唯一确定的增加头指针也能使双链表上的某些运算变得方便将头结点和尾结点链接起来也能构成循环链表并称之为双向链表设指针P指向某一结点则双向链表结构的对称性可用下式描述：（p）下一个即结点* P的存储位置既存放在其前趋结点*（P 之前）的直接后继指针域中也存放在它的后继结点*（P 下）的直接前趋指针域中双向链表的前插操作算法如下：无