数据结构英文版课件Chapter2.String-and-Character-Manipulation

1、Data Structures Using CNicklaus Wirth:1/36Data Structures计算机学院计算机学院 谢芳谢芳2/30Data Structures 2. String and Character Manipulation (using List Structure)IntroductionPrimitive Functions of Operations on Strings Representation of String String Manipulation in C Strings Manipulation ApplicationAlphabet:

2、An alphabet is a symbol from the set V, where V is an finite nonempty set of symbols.AlphabetV,V=symbol.#Examples: 2, s, String: An string is a sequence of characters or symbols. It is a concatenation of characters from the set V.StringS, S=c1c2, ciV, V=symbol.#Examples: “scut”, “2”,“s”,”HBUT”3/30Da

3、ta Structures 2.1 Introduction2.String and Character Manipulation2.String and Character Manipulation4/30Data Structures2.2 Primitive FunctionsOf Operations on Strings(1)Create a string of text;(2)Concatenate two strings to form a third string; (3)Search and replace a given substringwithin a string;(

4、4)Test for the identity of a string; (5)Compute the length of a string; (6)Insertion of a word within a string; (7)Deletion a word from a string.2.String and Character Manipulation Methods of the on Strings(1) Create(a) construct a respresentation of a string;(b) retain the value of a string in a va

5、riable.#Example: char str20;if str=“South China”;(2) Concatenation#Example: char str110, str210, str20; if str1=“South ”;if str2=“China”; str=“South China”;5/30Data Structures2.String and Character Manipulation(3) Search and Replace(a) a given string is searched inthe string from first character to

6、the last;(b) if a match is found, remove it;(c) save the position of the match;(d) a new string is inserted at the position of the match.#Example: char str10,str110, str210;Search:in:str1=“ing”; str=“String”;Replace: str2=“ong”; str1=“Strong”;Searching: ingmatchStringongReplace:6/30Data StructuresC.

7、 X. Deng 理学院理学院 物理系物理系 2.String and Character Manipulation(4) Test for the identity(a) a given substring is searchedin the string on a character-by-character from first character to the last;(b) if a match is found,TRUE is return otherwise FALSE is returned.#Example: char str10,str110, str210;Search

8、: Test in:str1=“ing”; str=“Strings”;Searching: ingmatchStringsTRUEStripSearching: ingno matchFALSE7/302010-3-30Data Structures Using CC. X. Deng 理学院理学院 物理系物理系 2.String and Character Manipulation(5) Computing the length(a) initialize length=0;(b) pointing the cursor to the first character;(c) if the

9、cursor is at the end of the string, output the length result, else do:(i) length=length+1;(ii) move the cursor to the next character;(d) repeat step (c).#Example:char str10; if str1=“Raman”;length=5;8/302010-3-30Data Structures Using C2.String and Character Manipulation(6) Insert(a)the inserted posi

10、tion of the original string oristr is p;(b) set the size of target string tarstr to be the length=original length +length of the inserted string insstr;(c)extract the characters of the original string up to the position p-1, and store it in the target string;(d) insert the string insstr;(e)extract t

11、he remaining characters from position p; placed it at the end of the target string;#Example: char oristr10, insstr4, tarstr20; oristr=“Bed Roses”; insstr=“of ”; inserted position: p=5 tarstr=“Bed of Roses”;9/30Data Structures2.String and Character Manipulation(6) Delete(a)Accept the substring delstr

12、 to be deleted from the original string oristr;(b) Checking whether delstr is in oristr;(c)set p is the starting position of the match of the substring delstr;(d) find the length L of the substring delstr;(e)Place the first p-1 characters from the original string in the target string tarstr;(f)extra

13、ct the remaining characters starting from the position (p+1) in the original string oristr and place it at the end of the target string tarstr;#Example: char oristr20, tarstr10;oristr=“Bed of Roses”; tarstr=“Bed”;deleted position: p=4 length: 910/30Data StructuresC. X. Deng 理学院理学院 物理系物理系 2.String an

14、d Character Manipulation11/302010-3-30Data Structures Using C2.3 Representation of String(1) Fixed length string method(2) Workspace and index table method(3) Linked list method2.String and Character Manipulation(1) Fixed length string method (Sequential List)#Example: char *str;str=“CHINA”;012345Ad

15、vantage:simple.Disadvantage:possible wastage of memory space; complex operations.str0str19NULL6 .1912/30Data StructuresC H IN A0. ADT of Sequential List (Fixed length string method )u Use this method to construct a string, data items occupy the sequential postions. Usually, string is stored in an ar

16、ray, and the length is fixed. Examples: int data10; char str10; We define the structure of string as a abstract data type. When you need use such data type in programs, you can declare one object of this structure and do not need to define its structure anymore. This is reuse technology.u There are

17、two different approach to define the structure of Sequential List:u Static approach to apply memory positions: typedef struct Elemtype data100; int len; SeqList; Declare data type: typedef int/char Elemtype;(at the beginning) u Dynamic approach to apply memory positions: typedef struct Elemtype *dat

18、a; int len; int listsize; SeqList_d; data=(Elemtype *)malloc(listsize*sizeof(Elemtype); u The storage structure of Sequential List is shown as following:u SeqList L;Functions Of Operations on Sequential Listu InitList()u LocateElem ()u ListInsert()u ListDelete()Functions Of Operations on Sequential

19、Listu Initalize a List L(static approach)int InitList_sq(SqList *L)(*L).len = 0;return 0; / Success Functions Of Operations on Sequential Listu Locate a data item from a Listint LocateElem_sq(SqList L, ElemType e) int i; if(1 = ListEmpty_sq(L) return 0; /failure for(i = 0; i L.len & L.datai != e; i+

20、); if(i L.len) return i + 1; /reture the position return 0; /failureFunctions Of Operations on Sequential Listu Initalize a List L(dynamic approach) Require the inclusion of stdlib.hint InitList_sq_d(SqList_d *L) (*L).data = (ElemType*)malloc(MAX*sizeof(ElemType); if(NULL = (*L).data) return -1; (*L

21、).listsize = MAX; (*L).len = 0; return 0; Require the inclusion of stdlib.h #include “stdlib.h” (*L).data = (ElemType*)malloc(MAX*sizeof(ElemType); Warning: malloc(MAX*sizeof(ElemType) is legal, but it doesnt allocate enough space for a structure. It allocates space only for a pointer. At here, date

22、 is a pointer, and the type of it is needed to convert to ElemType.typedef int ElemTypeFunctions Of Operations on Sequential ListuInsert a data item into a List (assumption:at the fourth position)int ListInsert_sq(SqList *L, int i, ElemType e) int j; if(i (*L).len + 1) return -1; if(1 = ListFull_sq(

23、*L) return -2; for(j = (*L).len; j = i; j-) (*L).dataj = (*L).dataj-1; (*L).datai-1 = e; (*L).len+; return 0; int ListInsert_sq_d(SqList_d *L, int i, ElemType e) int j, tempsize; ElemType *p = NULL; if(i (*L).len + 1) return -1; if(1 = ListFull_sq_d(*L) tempsize = (*L).listsize + INCSIZE; p = (ElemT

24、ype *)realloc(data,tempsize * sizeof(ElemType); if(NULL = p) return -2; (*L).data = p; (*L).listsize = tempsize; for(j = (*L).len; j = i; j-) (*L).dataj = (*L).dataj-1; (*L).datai-1 = e; (*L).len+; return 0; Functions Of Operations on Sequential ListuInsert a data item into a List (assumption:at the

25、 fourth position)int ListDelete_sq(SqList *L, int i, ElemType *e) int j; if(i (*L).len) return -1; if(1 = ListEmpty_sq(*L) return -2; *e = (*L).datai - 1; for(j = i + 1; j next = NULL; return 0; /successu Initialize a single Linked List u Initialize a single Linked List int CreateList_link_head(Link

26、List head, int n) int i; LNode *p = NULL; ElemType temp; if(n = 1; i-) p = (LNode *)malloc(sizeof(LNode); if(NULL = p) return -2; printf(“please input no.%d datas value:n”, i); scanf(“%d”, &temp); p - data = temp; p - next = head - next; head - next = p; return 0; u Locate a data item from a single

27、Linked List int LocateElem_link(LinkList head, ElemType e) int count = 1; LNode *p = head - next; while(NULL != p & p - data != e) p = p - next; count +; if(NULL = p) return 0; return count;u Insert a data item into a single Linked List int ListInsert_link(LinkList head, int i, ElemType e) int count

28、 = 0; LNode *p = head, *q = NULL; while(count next; count+; if(count i 1 | NULL = p) return -1; q = (LNode *)malloc(sizeof(LNode); if(NULL = q) return -2; /failure q - data = e; q - next = p; p - next = q; retrun 0; u Delete a data item from a single Linked List int ListDelete_link(LinkList head, in

29、t i, ElemType *e) int count = 0; LNode *p = head, *q = NULL; if(1 = ListEmpty_link(head) return -1; / the list is empty while(count next) p = p - next; count+; if(count i 1 | NULL = p - next) return -2; / have not this data item q = p - next; *e = p - data; p - next = q - next; free(q); /release the

30、 memory space retrun 0; header40data nextS20C30U10T40 70 Linked list method2.String and Character ManipulationPhysical Space T40C30U10S200010203040(header) 70 Circular singly39/30Data Structures 40struct node char data;struct node *next; struct node *header, *string;Address: Circular doublyLinked li

31、st methodstruct nodestruct node *prev; chardata;2.String and Character Manipulationstruct node *next; struct node *header, *string;datanextprev10 S 20403070 header40/30Data Structures Using CPhysical Space00102040(header) 70Address:40 C 3020 U 1030 T 4040C3030T4020U1010S20NULL4053#Example:length hea

32、der12Circular doubly Linked list method2.String and Character ManipulationJAI2 header41/30Data StructuresRAMAN1 header#Example: Circular doublyLinked list method2.String and Character Manipulationstruct nodestruct node *prev; char data;struct node *next; *fp=NULL, *lp=NULL;datanextprev42/30Data Stru

33、ctures Using Ccreation( )struct node *pf, *pp, *pf1; char ch;printf(“nEnter # to stop entering data”); while(1)scanf(“%c”, &ch); if (ch=#) break;else /*If the circular doubly linked list is empty.*/if (fp=NULL)/*fp: record the header*/ fp=(struct node *)malloc(sizeof(struct node); fp-prev=NULL; fp-d

34、ata=ch; fp-next=fp;pf=fp; /*end of if(fp=NULL)*/#Example: Circular doublyLinked list method2.String and Character Manipulationchfp:pf:43/30Data Structures/*If the circular doubly linked list contains some nodes.*/else/*If the circular doubly linked list contains some nodes*/./*else of “if(fp=NULL)”*/pp=fp;while (pp-next!=fp) pf=pp; pp=pp-next; /* if(fp!=NULL) find tail. pp=fp*/;pp-next=(struct